[BOJ 2468 C++] 안전영역

2468번: 안전 영역

문제 분석 및 풀이 방식

• 강수량을 지역의 높이의 최대값부터 최소값까지로 정한다.
• 각 값보다 높은 지역을 안전 지역으로 취급한다.
• 안전지역을 그래프의 요소로 취급하여 센다.
• 그래프의 요소를 셀때 dfs(깊이 우선 탐색)을 사용한다.
• 인접한 안전지역에 속한 칸을 탐색할 때 x, y의 좌표에 대한 배열을 이용하여 현재 좌표에서 상하좌우를 탐색한다.

#include <iostream>
#include <queue>

using namespace std;

int n, top, rain, cnt, ans;
int land[101][101];
bool safe[101][101];
bool depth[101][101];
int xDir[4] = {0, 1, 0, -1};
int yDir[4] = {1, 0, -1, 0};

void dfs(int x, int y) {
    depth[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int nextX = x + xDir[i];
        int nextY = y + yDir[i];
        if (depth[nextX][nextY] || !safe[nextX][nextY]) continue;
        if (0 <= nextX && nextX < n && 0 <= nextY && nextY < n)
            dfs(nextX, nextY);
    }
}

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> land[i][j];
            if (land[i][j] > top)
                top = land[i][j];
        }
    }
    for (rain = 0; rain <= top; rain++) {//비 안올때 부터 다잠길 때 까지
        cnt = 0;
        for (int i = 0; i < n; i++) {//초기화
            for (int j = 0; j < n; j++) {
                depth[i][j] = false;
                safe[i][j] = false;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                safe[i][j] = (land[i][j] > rain);//강수량 보다 높은 땅이면 안전 지대
        }
        for (int i = 0; i < n; i++) {//안전영역 세기
            for (int j = 0; j < n; j++) {
                if (safe[i][j] && !depth[i][j]) {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        if (ans < cnt)
            ans = cnt;
    }
    cout << ans;
    return 0;
}

배운 점

• x, y좌표에 대한 배열을 이용하여 상하좌우를 탐색하는데에 익숙해 지기 시작했다.
• 이 문제는 "11724번 연결요소의 개수" 문제와 유사한 점이 많은 것 같다.