[BOJ] 2468. 안전 영역 (C++)

문제

장마철에 물에 잠기지 않는 안전한 영역의 최대 개수 출력

장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다

생각할 것

각 높이마다 안전한 영역의 개수가 다르다.

왼쪽은 4 이하인 지점이, 오른쪽은 6이하인 지점이 모두 잠긴 경우 영역의 개수이다.

코드

#include <iostream>
#include <vector>

using namespace std;

int N;
int dx[4] = {-1, 1, 0, 0}; // 상하좌우
int dy[4] = {0, 0, -1, 1};
vector<vector<int>> board;
vector<vector<bool>> visited;

void dfs(int x, int y, int height) {
    visited[x][y] = true;
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        if (visited[nx][ny]) continue;
        if (board[nx][ny] > height) dfs(nx, ny, height);
    }
}

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

    cin >> N;

    board.assign(N, vector<int>(N));
    int maxHeight = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
            maxHeight = max(maxHeight, board[i][j]);
        }
    }

    int res, safe = 0;
    for (int height = 0; height <= maxHeight; height++) {
        safe = 0;
        visited.assign(N, vector<bool>(N));
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] > height && !visited[i][j]) { // 잠기지 않는 영역 시작
                    dfs(i, j, height);
                    safe++;
                }
            }
        }
        res = max(res, safe);
    }

    cout << res;
    return 0;
}