안전 영역

작성일 | In

[백준] 2468번 - 안전 영역

문제 링크

KOI 2010 초등부 문제.
내릴 수 있는 비의 모든 경우의 수를 따져 bfs로 풀면 되는 문제이다.
단, 모든 지역의 높이가 같은 경우 안전 영역의 최대 개수는 1개이다. 이 경우만 예외처리해주면 된다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

int n, rain, area, ans;
int field[100][100];
queue<pair<int, int>> que;
vector<vector<bool>> visited; 

void bfs(int i, int j) {
    visited[i][j] = true;
    que.push({i,j});

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

        for(int i=0; i<4; ++i) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
            if(field[ny][nx] <= rain) continue; 
            if(visited[ny][nx]) continue;

            visited[ny][nx] = true;
            que.push({ny, nx});
        }
    }
    ++area;
}

int main(void) {
    // 가장 낮은 지역의 높이보다 적게 비가 오거나,
    // 가장 높은 지역의 높이보다 같거나 많이 비가 오면
    // 안전 영역의 개수는 1개, 0개이므로 bfs를 할 필요가 없다.
    int shortest=101, tallest=0;

    scanf("%d", &n);
    for(int i=0; i<n; ++i) {
        for(int j=0; j<n; ++j) {
            scanf(" %d", &field[i][j]);
            shortest = min(shortest, field[i][j]);
            tallest = max(tallest, field[i][j]);
        }
    }

    visited.resize(n);
    for(int i=0; i<n; ++i)
        visited[i].resize(n, false);

    for(int i=shortest; i<=tallest; ++i) {
        rain = i; area = 0;
        for(int j=0; j<n; ++j) {
            for(int k=0; k<n; ++k) {
                if(!visited[j][k] && field[j][k] > rain)
                    bfs(j,k);
            }
        }
        // 현재 rain에 대해 bfs를 진행했는데 안전 영역이 0개라면, 
        // 모든 지역의 높이가 같은 경우이다.
        // 이 때는 최대 안전 영역 개수를 1로 예외처리한다.
        if(area == 0)
            area = 1;
        ans = max(ans, area);
        for(int i=0; i<n; ++i)
            fill(visited[i].begin(), visited[i].end(), false);
    }
    printf("%d", ans);
}
0%