BOJ 2468: 안전 영역

✔ 문제 링크

BOJ 2468: 안전 영역

✔ 문제해결전략

• 그래프 탐색
• BFS(Breadth First Search)

✔ 해결과정

• BFS를 여러 번 돌리며 각 사이클에서 물에 잠기지 않는 영역의 개수를 구해 비교하며 최댓값을 찾으면 된다
• 강수량 1부터 BFS 돌리니 99%쯤에서 틀렸습니다가 떠서 당황했는데 문제를 자세히 보니 아래 노트에 "아무 지역도 물에 잠기지 않을 수도 있다."고 적혀있었다.
• 모든 건물의 높이가 1인 경우도 있으니 여기서 아무 지역도 물에 잠기지 않으려면 강수량 0도 고려를 해야 한다. 0부터 탐색을 시작하니 정답이었다

✔ 정답 Code

#include <bits/stdc++.h>
using namespace std;

int m[100][100];
int vis[100][100];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, maxH = -1;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> m[i][j];
            if (m[i][j] > maxH) maxH = m[i][j];
        }
    }

    int ans = -1;
    int cnt = 0;
    for (int h = 0; h <= maxH; h++) {

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (vis[i][j] != 0 || m[i][j] <= h) continue;
                queue < pair < int, int > > Q;
                vis[i][j] = 1;
                Q.push({
                    i,
                    j
                });
                while (!Q.empty()) {
                    auto cur = Q.front();
                    Q.pop();
                    for (int dir = 0; dir < 4; dir++) {
                        int nx = cur.first + dx[dir];
                        int ny = cur.second + dy[dir];
                        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                        if (vis[nx][ny] != 0 || m[nx][ny] <= h) continue;
                        vis[nx][ny] = 1;
                        Q.push({
                            nx,
                            ny
                        });
                    } // for
                } // while
                cnt++;
            } // j
        } // i
        ans = max(ans, cnt);
        cnt = 0;
        memset(vis, false, sizeof(vis));
    } // h
    cout << ans << '\n';
}

✔ Check Point

• 각 사이클 끝나고 다음 사이클에 들어가기 전에 vis 초기화해야 한다는 것 주의