Algorithm/백준
[BOJ] - 2468. 안전 영역
benguin
2019. 8. 20. 14:50
[URL]
https://www.acmicpc.net/problem/2468
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어
www.acmicpc.net
[풀이 과정]
1. 입력
2. 가능한 경우 (물의 높이: 1 ~ 지면의 최대 높이까지만!)
3. 맵 복사
4. 물 퍼트리기 : c_map[][] = -1;
5. 안전영역 계산 : BFS()
6. 안전영역 갯수 최대값(Max) 구하기
[소스 코드]
|
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
#include <stdio.h>
#include <queue>
using namespace std;
int N;
int map[101][101];
int c_map[101][101];
bool check[101][101];
int max_height = -1;
int Max = 1;
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
void input() {
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
scanf("%d", &map[i][j]);
max_height = max(map[i][j], max_height);
}
}
}
void copyMap(int waterHeight)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (map[i][j] <= waterHeight)
{
c_map[i][j] = -1;
}
else
{
c_map[i][j] = map[i][j];
}
}
}
// check[][] 배열 초기화
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
check[i][j] = false;
}
}
}
void BFS(int sx, int sy) {
queue <pair<int, int>> q;
// 안전영역은 -99로 채워준다.
q.push(make_pair(sx, sy));
check[sx][sy] = true;
c_map[sx][sy] = -99;
while (!q.empty())
{
int cx = q.front().first;
int cy = q.front().second;
q.pop();
for (int k = 0; k < 4; k++)
{
int nx = cx + dx[k];
int ny = cy + dy[k];
if (nx >= 0 && nx < N && ny >= 0 && ny < N)
{
if (check[nx][ny] == false && c_map[nx][ny] != -1 && c_map[nx][ny] != -99)
{
q.push(make_pair(nx, ny));
check[nx][ny] = true;
c_map[nx][ny] = -99;
}
}
}
}
}
int spread()
{
// 안전영역 갯수 계산
int areaCnt = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (c_map[i][j] != -1 && c_map[i][j] != -99)
{
areaCnt++;
BFS(i, j);
}
}
}
return areaCnt;
}
void go() {
for (int w = 1; w <= max_height; w++)
{
copyMap(w);
int tempVal = spread();
Max = max(tempVal, Max);
}
}
int main() {
input();
go();
printf("%d\n", Max);
return 0;
}
|
cs |