백준 2468번 안전 영역 - C++(cpp) 풀이

---

 

1. 물에 잠기지 않은 지역을 정점으로 생각하고 상하좌우로 인접한 정점을 간선으로 이었을 때, 그래프의 연결 요소가 곧 안전 영역이다.
2. 그래프의 연결 요소 개수는 모든 정점을 방문하기 위해 호출해야 하는 DFS/BFS 횟수와 같다.
3. 가능한 모든 높이에 대해 해당 높이만큼 물이 찼을 때 안전영역의 개수를 센 뒤, 최댓값을 찾는다.

 

1. 물에 잠기지 않은 지역을 정점으로 생각하고 상하좌우로 인접한 정점을 간선으로 이었을 때, 그래프의 연결 요소가 곧 안전 영역이다.

 주어진 상황을 그래프로 바꾸어 생각할 수 있다. 물에 잠기지 않은 지역을 정점으로 생각하고, 상하좌우로 인접한 정점들을 간선으로 이었을 때, 안전 영역은 그래프의 연결 요소와 같다.

 

2. 그래프의 연결 요소 개수는 모든 정점을 방문하기 위해 호출해야 하는 DFS/BFS 횟수와 같다.

 한 번의 DFS/BFS로 시작 정점이 속한 연결 요소의 모든 정점을 방문할 수 있으므로, 그래프의 총 연결 요소 개수는 모든 정점을 방문하기 위해 호출해야 하는 DFS/BFS 횟수와 같다.

 

3. 가능한 모든 높이에 대해 해당 높이만큼 물이 찼을 때 안전영역의 개수를 센 뒤, 최댓값을 찾는다.

 가능한 모든 높이 h=0~100에 대해, 해당 높이만큼 물이 찼을 때 안전영역의 개수를 구한 뒤, 그중 최댓값을 찾아주면 된다. 한 번의 DFS/BFS에 O(N^2)의 시간 복잡도가 소요되므로, 전체 시간복잡도는 O(N^3).

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

const int MAX = 101;

int N;
int board[MAX][MAX];
bool visit[MAX][MAX];

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

void DFS(int r, int c, int h) {
    visit[r][c] = true;
    
    for (int i=0; i<4; i++) {
        int next_r = r + dr[i];
        int next_c = c + dc[i];
        
        if (next_r < 0 || next_r >= N || next_c < 0 || next_c >= N) continue;
        if (board[next_r][next_c] <= h || visit[next_r][next_c]) continue;
        DFS(next_r, next_c, h);
    }
}

int find_max_safe_area() {
    int ret = 1;
    
    for (int h=1; h<MAX; h++) {
        int cnt = 0;
        
        memset(visit, 0, sizeof(visit));
        for (int r=0; r<N; r++) {
            for (int c=0; c<N; c++) {
                if (visit[r][c] || board[r][c] <= h) continue;
                
                DFS(r, c, h);
                cnt++;
            }
        }
        
        ret = max(ret, cnt);
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> board[i][j];
        }
    }
    
    cout << find_max_safe_area();

    return 0;
}