[BaekJoon/백준] 2468번 안전 영역

 

끝내 내 궁금증을 해결하지 못한 아쉬운 문제.

 

 

 

나는 물의 높이를

지형 중 가장 높은 경우일 때 부터 내림차순으로 진행했었다.

 

그렇게 하면, 안전한 지역들이 점점 드러나면서 증가되다가, 어느 순간 안전한 지역들끼리 합쳐져서 전체 안전한 지역이 줄어드는 그 순간에 조기종료를 해서 시간복잡도를 줄이려고 했었다.

 

정말 질문검색 탭에 있는 모든 테스트케이스는 다 맞는데, 왜 틀렸다고 나오는지 모르겠다...

심지어 비가 아예 오지 않는 경우도 잘 들어맞는다.. 뭐가 문제인지 정말 모르겠다.

 

 

그래서 그냥 완전탐색으로.. 조기종료 하지 않고 전체 경우를 모두 찾아 주게끔 코드를 변경해서 해결했다

#include <iostream>
#include <cstring>

/*
 아예 다 침수된것부터 시작(높이 중 가장 높은 값을 이용)
 그리고 침수높이를 점점 낮추면서 dfs.
 
 dfs 값(안전한 영역) 변화가 내림차순이 아니게 된다면 멈춤.
 전체 안전한 지역 갯수가 처음에 증가하다가, 안전한 지역끼리 합쳐져서 전체 안전한 지역 갯수가 줄어드는 순간에 종료.
 */


/*
 로 하려 했는데, 물의 높이를 최대에서부터 해서 조기종료를 하려니까 틀렸습니다 x 10
 
 조기종료가 불가능한 완전탐색 문제였다. 내림차순이 아니게 되어도 진행해야한다.

 
 사실 왜 내 방법대로 조기종료가 불가능한지, 왜 전체 다 탐색해주어야만 하는진 확실히 모르겠다.

 */


using namespace std;

int N;

int MAP[100][100];

//bool SAFTY[100][100]; // 안전하면 true, 아니면 false
bool VISIT[100][100];

int MAX_SAFTY = -1, SAFTY;

int FLOOD; // 침수 높이


int mx[4] = {0, 0, 1, -1};
int my[4] = {1, -1, 0, 0};


void dfs(int x, int y) {
    
    
    VISIT[x][y] = true;
    
    
    for(int i = 0; i < 4; i++) {
        
        int tx = x + mx[i];
        int ty = y + my[i];
        
        
        if(tx < 0 || tx >= N || ty < 0 || ty >= N)
            continue;
        
        if(MAP[tx][ty] > FLOOD && !VISIT[tx][ty])
            dfs(tx, ty);
        
    }
    
    
    
}

int main() {
    
    cin >> N;
    
    
    for(int i = 0; i < N; i++) {
        
        for(int j = 0; j < N; j++) {
            
            cin >> MAP[i][j];
            
            if(FLOOD < MAP[i][j])
                FLOOD = MAP[i][j];
        }
    }
    
    while(FLOOD >= 0) { // 조기종료 없이 '모든 경우의 수'를 탐색해야 정답처리가 된다.
        
        SAFTY = 0;
        memset(VISIT, 0, sizeof(VISIT));
        
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                
                if(MAP[i][j] > FLOOD && !VISIT[i][j]) {
                    dfs(i, j);
                    SAFTY++;
                }
                
            }
        }
        
        if(MAX_SAFTY < SAFTY)
            MAX_SAFTY = SAFTY;
        // 여길 주석해줘야 맞는다.. 조기종료를 하면 틀린다.
//        else // 안전한 지역이 줄어드는 형태라면 반복 종료.
//            break;
        
        
        FLOOD--; // 물을 감소
    }
    
    cout << MAX_SAFTY << "\n";
    
    
    
    
}

 

 

소요 시간 : 1시간