문제 출처

1. 문제설명

  • N*N크기의 영역이 주어진다.
  • 각 칸에는 높이가 적혀있다.
  • 비가 내리면 일정 높이의 지점이 물에 잠기게 된다.
  • 이때 잠기지 않은 영역의 개수를 구하는 문제이다.
  • 비가 많이 와서 모든 지역이 잠길 수도 있고, 적게 와서 일부 지역만 잠길 수도 있는데,
  • 안전 영역이 가장 많이 생기는 높이를 구하라.



2. 알고리즘 설계

  • 맵에 높이를 입력받게 된다.
    • 이 때, 맵의 최대 값을 갱신한다.
  • 0부터 맵의 최대값까지 물에 잠기는 상황을 고려해 탐색한다.
    • for(int limit=0; limit<=upper; limit++)
  • limit보다 작은 지점을 BFS 탐색한다.
    • 탐색이 끝나면, 영역 하나가 계산된 것이므로 카운팅한다.
  • 위와 같은 방식을 최대값까지 계산해, 카운팅이 가장 큰 값을 출력하면 된다!



3. 전체 코드

#include <bits/stdc++.h>
#define Y first
#define X second

using namespace std;
using pii = pair<int,int>;

const int SZ = 100;
const int dy[] = {-1,1,0,0};
const int dx[] = {0,0,-1,1};
int n, board[SZ][SZ];
bool visited[SZ][SZ];
int upper = 0;

void bfs(pii src, int limit) {
    queue<pii> q;
    q.push(src);
    visited[src.Y][src.X] = true;

    while(!q.empty()) {
        pii cur = q.front();
        q.pop();

        for(int dir=0; dir<4; dir++) {
            int ny = cur.Y + dy[dir];
            int nx = cur.X + dx[dir];

            if(ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
            if(visited[ny][nx] || board[ny][nx] <= limit) continue;

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

int solve(int limit) {
    int ret = 0;
    fill_n(&visited[0][0], SZ*SZ, false);

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(board[i][j] > limit && !visited[i][j]) {
                bfs({i, j}, limit);
                ret++;
            }
        }
    }

    return ret;
}

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

    int ans = 0;

    cin >> n;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> board[i][j];
            upper = max(upper, board[i][j]);
        }
    }

    for(int limit=0; limit<=upper; limit++)
        ans = max(solve(limit), ans);

    cout << ans;
    return 0;
}