https://www.acmicpc.net/problem/16234
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명
www.acmicpc.net
BFS를 이용해서 인접해 있는 칸(국가)들의 인구를 비교해주고 국경선을 열어줄 수 있다.
이 문제는 일종의 연결 요소 문제인 것 같다. 연결되어 있는 나라들(한 번의 BFS탐색으로 탐색이 가능한 나라들)에 같은 번호를 붙여주고 같은 번호가 붙어있는 나라들끼리 인구이동을 해주면 된다.
인구 이동은 인구이동이 발생하지 않을 때까지 진행한다.
인구이동을 진행하기 위해서는 모든 국가들을 탐색하여 연합국가를 만들어준다.
연합국가에 이미 포함된 국가들은 방문 체크를 통해 다시 탐색하지 않는다.
어렵지 않으므로 자세한 설명은 코드 참고!
|
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
|
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int n, l, r;
int ans;
int map[50][50];
int check[50][50];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
//bfs로 인접한 국가를 탐색
bool bfs(int x, int y, int num) {
queue<pair<int, int>> q;
q.push(make_pair(x, y));
check[x][y] = num;
//시작칸의 국가의 인구수도 sum에 더해주고 처음 연함국가 수는 1
int sum = map[x][y];
int cnt = 1;
while (!q.empty()) {
x = q.front().first;
y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
//범위 체크
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
//방문 체크
if (check[nx][ny] != 0) continue;
//두 국경사이의 인구 차이를 계산하고 차이가 l보다 작거나 r보다 크면 국경선을 열지 않는다
int diff = map[x][y] - map[nx][ny];
if (diff < 0) diff = -diff;
if (l > diff || diff > r) continue;
q.push(make_pair(nx, ny));
check[nx][ny] = num;
//연합을 할 국가들의 인구수를 모두 더해준다.
sum += map[nx][ny];
//연합이 될 국가의 수 증가
cnt++;
}
}
//cnt값이 초기값보다 증가 했다면 인구 이동이 있었다
if (cnt > 1) {
//연합을 이루는 국가들의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다
int newnum = sum / cnt;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (check[i][j] == num) {
map[i][j] = newnum;
}
}
}
return true;
} //인구 이동이 없었다
else return false;
}
//모든 국가에 대해서 탐색
bool solve() {
bool flag = false;
int num = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (check[i][j] == 0) {
if (bfs(i, j,num++)) {
//한번이라도 인구이동이 있으면 true
flag = true;
}
}
}
}
if (flag) return true;
else return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> l >> r;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
}
}
while (true) {
//인구 이동을 더 이상 할 수 없으면 break
if (!solve()) break;
ans++;
memset(check, 0, sizeof(check));
}
cout << ans << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 15685. 드래곤 커브 (0) | 2019.08.04 |
|---|---|
| [BOJ] 15686. 치킨 배달 (0) | 2019.08.04 |
| [BOJ] 17281. ⚾ (0) | 2019.08.02 |
| [BOJ] 17136. 색종이 붙이기 (0) | 2019.08.02 |
| [BOJ] 17135. 캐슬 디펜스 (0) | 2019.08.01 |