Algorithm/백준
[BOJ] - 16234. 인구 이동
benguin
2019. 4. 12. 12:31
[URL]
https://www.acmicpc.net/problem/16234
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명
www.acmicpc.net
[풀이 과정]
* DFS (기존 단지번호 붙이기 문제와 유사)
1. 그룹화가 우선 --> 그룹이 생기지 않으면 종료
2. bool isGroupPossible() : 그룹화
이중 for문을 돌려 해당위치와 상하좌우 비교하여 인구수 차이 L 이상 R이하인 경우 그룹화 가능
3. DFS() : check[]][ 업데이트
그룹화 가능하면 DFS로 check배열 업데이트
각 그룹 별로 check[][] = groupCnt
4. populationMovement() : 인구이동
각group[][] = group 전체의 합계 / group 전체의 갯수 업데이트
5. 그룹이 더 이상 생기지 않을시 종료
최종적으로 인구이동 몇번 발생했는지, resCnt 출력
[소스 코드]
|
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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
#include <stdio.h>
#include <algorithm>
using namespace std;
// variable
int N, L, R;
int A[55][55];
int check[55][55];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int resCnt = 0;
// func
void init();
bool isGroupPossible(int cx, int cy) {
for (int k = 0; k < 4; k++)
{
int nx = cx + dx[k];
int ny = cy + dy[k];
if (nx >= 0 && ny >= 0 && nx < N && ny < N)
{
int diff = abs(A[cx][cy] - A[nx][ny]);
if (diff >= L && diff <= R)
{
return true;
}
}
}
return false;
}
void DFS(int cx, int cy, int groupCnt)
{
check[cx][cy] = groupCnt;
for (int k = 0; k < 4; k++)
{
int nx = cx + dx[k];
int ny = cy + dy[k];
if (nx >= 0 && ny >= 0 && nx < N && ny < N)
{
int diff = abs(A[cx][cy] - A[nx][ny]);
if (diff >= L && diff <= R && check[nx][ny] == 0)
{
DFS(nx, ny, groupCnt);
}
}
}
}
void populationMovement(int groupCnt)
{
for (int t = 1; t <= groupCnt; t++)
{
int tempSum = 0;
int tempCnt = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (check[i][j] == t)
{
tempSum += A[i][j];
tempCnt++;
}
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (check[i][j] == t)
{
A[i][j] = tempSum / tempCnt;
}
}
}
}
}
int main() {
init();
while (true)
{
// check[][] 초기화
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
check[i][j] = 0;
}
}
int groupCnt = 0;
// DFS
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (isGroupPossible(i, j) && check[i][j] == 0)
{
groupCnt++;
DFS(i, j, groupCnt);
}
}
}
// 인구이동 판별
if (groupCnt == 0)
break;
else
{
//인구이동 스타트
populationMovement(groupCnt);
resCnt++;
}
}
printf("%d\n", resCnt);
return 0;
}
void init() {
scanf("%d %d %d", &N, &L, &R);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
scanf("%d", &A[i][j]);
}
}
}
|
cs |