문제 주소 : www.acmicpc.net/problem/16234
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
문제 확인
전형적인 DFS, BFS 그레프 탐색 문제입니다.
* 문제에 자세하게 나오지 않아 헷갈리는 부분이 있는데 같은 날에서 여러 개의 연합이 인구이동을 할 수 있고 이는 한 번으로 취급됩니다.
이 문제에서 해결해야 할 점은 2개입니다.
1. 조건에 맞춰 국가 연합 생성, 생성할 연합이 그 단계에 없다면 종료
2. 연합에 속해 있는 나라의 인구 변경
풀이
배열 초기화 시 배열 외부의 점을 탐색하는 조건절을 단순화하기 위해 배열의 테두리를 지정합니다.
연합 생성은 DFS로 탐색하였습니다. 탐색 조건은 테두리(-1)가 아니고 방문하지 않은 점, 문제에 주어진 조건으로 3가지를 지정하였습니다.
탐색 시 조건에 맞는 나라는 모두 스택에 저장하고 모든 나라의 탐색이 끝나면 스택에 저장해둔 나라들의 새로운 인구수를 저장합니다.
인구 이동이 일어나지 않은 점 들은 인구수가 변동이 없으므로 다음 단계의 인구이동을 탐색할 때 전 단계에서 인구이동이 일어난 나라, 그 나라들의 상하좌우에 있는 나라만 탐색을 합니다. 이를 통해 탐색 횟수를 크게 줄일 수 있었습니다.
코드
|
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
|
#include <cstdio>
#include <cstring>
#include <cstdlib>
typedef struct point {
int x, y;
}point;
int dx[4] = { 1, -1, 0, 0 },
dy[4] = { 0, 0, 1, -1 },
N, L, R, top, val, cnt, list_cnt;
int ary[52][52], visit[52][52];
point stack[2501], list[2501];
void dfs(int x, int y) {
if (visit[x][y]) return;
visit[x][y] = 1;
stack[top++] = { x, y };//탐색한 위치 저장
val += ary[x][y];
for (int d = 0; d < 4; d++) {
int tx = dx[d] + x, ty = dy[d] + y, gap = abs(ary[tx][ty] - ary[x][y]);
if (ary[tx][ty] != -1 && !visit[tx][ty] && L <= gap && gap <= R) { //조건에 맞는 나라 탐색
dfs(tx, ty);
}
}
if (top > 1 && x == stack[0].x && y == stack[0].y) { //인구 이동할 모든 나라를 찾으면 탐색한 나라 값 변경
val /= top;
for (int i = 0; i < top; i++) {
ary[stack[i].x][stack[i].y] = val;
list[list_cnt++] = { stack[i].x , stack[i].y };
}
cnt = 1;
}
}
int main() {
int tcnt = 0;
scanf("%d%d%d", &N, &L, &R);
for (int i = 0; i <= N; i++)
ary[0][i] = ary[i][0] = ary[N + 1][i] = ary[i][N + 1] = -1;//태두리
for (int i = 1, j = 1; i <= N; i++, j = 1)
while (j <= N)
scanf("%d", &ary[i][j++]);
for (int i = 1; i <= N; i++)
for (int j = (i & 1) + 1; j <= N; j += 2) {//탐색한 점의 상하좌우는 다시 탐색할 필요 없음 -> 격자 모양으로 탐색
dfs(i, j);
top = 0; val = 0;
}
point tmp_list[2501];
if (cnt) {//첫 단계에 인구 이동이 일어나면 다음 단계에서는 인구 이동이 일어난 나라와 그 나라의 상하좌우만 탐색하면 됨
for (tcnt++; cnt; tcnt++) {
memset(visit, 0, sizeof(visit));
cnt = 0;
int tmp = list_cnt;
memcpy(tmp_list, list, sizeof(point) * list_cnt);
list_cnt = 0;
for (int i = 0; i < tmp; i++) {
dfs(tmp_list[i].x, tmp_list[i].y);
top = 0; val = 0;
}
}
}
printf("%d", tcnt > 0 ? tcnt - 1 : 0);
}
|
cs |
|
|
|
반응형
'알고리즘 문제 > [백준]' 카테고리의 다른 글
| [백준] 16235번 나무 재테크 (0) | 2020.11.02 |
|---|---|
| 백준 16637 괄호 추가하기 (0) | 2020.10.30 |
| 백준 15684 사다리조작 (0) | 2020.10.30 |
| 백준 14500 테트로미오 (0) | 2020.10.30 |
| 백준 12094: 2048(Hard) (0) | 2020.10.30 |