안전 영역 (feat. 백준, 2468번)

안전 영역
https://www.acmicpc.net/problem/2468

2468번: 안전 영역

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int N, dx[4], dy[4], arr[101][101], ans;
bool visit[101][101];
void bfs(register int height){
    memset(visit, false, sizeof(visit));
    for(register int i = 1, j; i <= N; ++i)
        for(j = 1; j <= N; ++j)
            if(arr[i][j] <= height)
                arr[i][j] = 0;
    register int tmp = 0;
    queue<pair<int, int>> q;
    for(register int i = 1, j; i <= N; ++i)
        for(j = 1; j <= N; ++j)
            if(!visit[i][j] && arr[i][j] > 0){
                ++tmp;
                q.push(make_pair(i, j));
                visit[i][j] = true;
                while(!q.empty()){
                    auto p = q.front(); q.pop();
                    register int x = p.first, y = p.second;
                    for(register int d = 0, nx, ny; d < 4; ++d){
                        nx = x + dx[d], ny = y + dy[d];
                        if(1 <= nx && nx <= N && 1 <= ny && ny <= N && !visit[nx][ny] && arr[nx][ny] > 0)
                            visit[nx][ny] = true, q.push(make_pair(nx, ny));
                    }
                }
            }
    ans = max(ans, tmp);
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
    register int min_height = 100, max_height = 1;
    cin >> N;
    for(register int i = 1, j; i <= N; ++i)
        for(j = 1; j <= N; ++j)
            cin >> arr[i][j], min_height = min(min_height, arr[i][j]), max_height = max(max_height, arr[i][j]);
    ans = 1;
    for(register int height = min_height; height < max_height; ++height)
        bfs(height);
    cout << ans;
    return 0;
}
// *&)*@*

 

 

1. 입력으로 주어진 높이 중 가장 낮은 높이부터 가장 높은 높이 이전까지만 탐색 해보면 됩니다.
2. 주어진 높이보다 낮은 영역은 0으로 변경합니다. 그리고 (1,1) 부터 (N,N)까지 방문한 적이 없고 0보다 큰 지역에 대해서 방문했음을 알리는 visit에 마킹을 합니다. 물론 방문하지 않은 지역에 도달하는 순간 안전 영역은 1 증가시켜줍니다.
3. 가장 낮은 높이부터 가장 높은 높이까지 2번을 수행하며 안전 영역을 모두 구하고 그 중 가장 큰 값을 출력합니다.