백준 2468 안전 영역 (C++)

2468번: 안전 영역

bfs를 활용한 문제이다. 장마철에 잠기는 높이가 주어지지 않기 때문에 0부터 최대 높이까지 모두 구해봐야한다. 0부터 구하는 이유는 비가 안 올 경우도 존재하기 때문이다. 구해야하는 값은 물에 잠기지 않은 구역의 갯수의 최댓값이므로 bfs를 이용해 구해주었다. 0부터 최대 높이 - 1 까지 반복문을 돌려주면서 bfs를 통해 구역 갯수를 구해주어 최댓값을 저장해 출력해주었다.
이번 문제는 이해하는데 시간이 좀 걸렸다. 비가 오지 않을 경우와 같은 특수 케이스도 생각을 해야겠다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

int N, m = 0, res = 0;
int A[100][100];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
bool visit[100][100];

void bfs(int rain, int a, int b) {
    queue<pair<int, int>> q;

    q.push({ a,b });

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
            if (visit[ny][nx]) continue;
            if (A[ny][nx] <= rain) continue;

            q.push({ ny,nx });
            visit[ny][nx] = true;
        }
    }
}

void solution(){
    for (int k = 0; k < m; k++) {
        memset(visit, 0, sizeof(visit));
        int tmp = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (A[i][j] > k && !visit[i][j]) {
                    bfs(k, i, j);
                    tmp++;
                }
            }
        }

        res = max(res, tmp);
    }

    cout << res;
}

int main() {
    ios::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 >> A[i][j];
            m = max(m, A[i][j]);
        }
    }

    solution();

    return 0;
}