[BOJ] 인구 이동 - 16234 (G4)
[BOJ] 인구 이동 - 16234 (G4)
| 시간 제한 | 메모리 제한 |
|---|---|
| 2 초 | 512 MB |
문제
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.
오늘부터 인구 이동이 시작되는 날이다.
인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.
- 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
- 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
- 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
- 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
- 연합을 해체하고, 모든 국경선을 닫는다.
각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)
인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.
출력
인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.
풀이
이 문제는 시뮬레이션과 BFS를 결합한 문제이다. 매일 국경선이 열리는 나라들을 찾아 연합을 만들고, 인구를 재분배하는 과정을 반복해야 한다.
접근 방법
인구 이동이 일어나는 하루는 다음과 같은 과정을 거친다:
- 연합 찾기: BFS를 사용하여 국경선이 열리는 나라들의 연합을 찾는다.
- 인구 재분배: 각 연합의 평균 인구수를 계산하고 재분배한다.
- 종료 조건 확인: 어떤 연합도 만들어지지 않으면 인구 이동 종료.
상세 풀이
1. 연합 찾기 (open 함수)
BFS를 사용하여 현재 위치에서 시작해 국경선을 열 수 있는 모든 나라를 탐색한다:
- 인접한 나라와의 인구 차이가 L 이상 R 이하면 국경선을 연다
- 연결된 모든 나라를 하나의 연합으로 묶는다
- 연합의 총 인구수를 계산하여 평균을 구한다
2. 인구 이동 (move 함수)
한 번의 인구 이동(하루) 과정:
- 방문 배열을 초기화한다
- 모든 위치를 순회하며 아직 방문하지 않은 나라에서 BFS를 시작한다
- 연합이 2개 이상의 나라로 이루어진 경우에만 결과에 추가한다
- 모든 연합에 대해 인구를 재분배한다
- 연합이 하나도 없으면 False를 반환하여 종료를 알린다
코드
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
from collections import deque
N, L, R = map(int, input().split())
populations = [list(map(int, input().split())) for _ in range(N)]
dyx = ((0, 1), (1, 0), (0, -1), (-1, 0))
def open(populations, start, visited):
'''
조건에 따라 국경선이 열리는 나라 찾기
'''
q = deque([start])
visited[start[0]][start[1]] = True
unite = [start]
while q:
y, x = q.popleft()
for dy, dx in dyx:
ny, nx = y + dy, x + dx
if not ((0 <= ny < N) and (0 <= nx < N)):
continue
if visited[ny][nx]:
continue
# 국경선을 열 조건이 아닌 경우
if not (L <= abs(populations[y][x] - populations[ny][nx]) <= R):
continue
unite.append((ny, nx))
q.append((ny, nx))
visited[ny][nx] = True
population_avg = 0
for y, x in unite:
population_avg += populations[y][x]
population_avg //= len(unite)
return unite, population_avg
def move(populations):
# 연합을 해체하고, 모든 국경선을 닫는다.
visited = [[False] * N for _ in range(N)]
result = []
# 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
for y in range(N):
for x in range(N):
if visited[y][x]:
continue
unite, unit_population = open(populations, (y, x), visited)
# 연합의 수가 1일 경우(국경을 열지 않았을 경우)
if len(unite) == 1:
continue
result.append((unite, unit_population))
# 어떤 국경도 열리지 않았을 경우
if not result:
return False
# 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
# 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
# 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
for unite, unit_population in result:
for y, x in unite:
populations[y][x] = unit_population
return True
day_cnt = 0
while True:
if not move(populations):
break
# print(*populations, sep='\n')
day_cnt += 1
print(day_cnt)
코드 설명
open 함수
- BFS를 사용하여 현재 위치에서 국경선을 열 수 있는 모든 나라를 탐색
- 인접한 나라와의 인구 차이가 L 이상 R 이하인 경우에만 연합에 포함
- 연합의 평균 인구수를 계산하여 반환
move 함수
- 한 번의 인구 이동(하루)을 처리
- 모든 위치를 순회하며 연합을 찾고, 2개 이상의 나라로 이루어진 연합만 처리
- 연합이 없으면 False 반환, 있으면 인구를 재분배하고 True 반환
메인 로직
move함수가 False를 반환할 때까지 반복- 매일마다 카운트를 증가시켜 최종 일수를 출력
시간 복잡도
- 한 번의
move함수: O(N²) (모든 칸을 방문) - 최악의 경우 2,000일까지 반복: O(2000 × N²)
- N ≤ 50이므로 2000 × 50² = 5,000,000번의 연산으로 충분히 시간 내에 해결 가능
주의 사항
- 연합 조건: 인구 차이가 정확히 L 이상 R 이하여야 한다.
- 단일 국가 처리: 연합이 1개 국가로만 이루어진 경우는 인구 이동이 없으므로 제외한다.
- 종료 조건: 어떤 연합도 만들어지지 않을 때 종료한다.
- 방문 배열 초기화: 매일 새로운 방문 배열을 사용해야 한다.
최적화 고려사항
문제에서 인구 이동 일수가 2,000일 이하임을 보장하므로, 시간 초과를 걱정하지 않아도 된다. 하지만 더 큰 입력에서는 변화가 있는 영역만 탐색하는 최적화를 고려할 수 있다.
This post is licensed under CC BY 4.0 by the author.