인구 이동(백준 16234번)
💡 **Check Point !
( 해당사항 ✓체크 )
막힘 없이 수월하게 풀린 문제인가?
1시간이내로 풀렸던 문제인가?
1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?
시간을 써도 도무지 풀 수 없는 문제인가?
솔루션을 찾아봤는가? ✓
난이도 체감
최상
상✓
중
하
이해도
완벽히 이해✓
다소 헷갈리는 부분들이 있음
이해 못함
문제
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.
오늘부터 인구 이동이 시작되는 날이다.
인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.
- 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
- 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
- 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
- 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
- 연합을 해체하고, 모든 국경선을 닫는다.
각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.
초기 상태는 아래와 같다.
https://upload.acmicpc.net/2993ef69-f57e-4d46-a9b3-eb3a05612dc7/-/preview/
L = 20, R = 50 이기 때문에, 모든 나라 사이의 국경선이 열린다. (열린 국경선은 점선으로 표시)
https://upload.acmicpc.net/3e73073e-b68e-478b-90fd-f158f44863b7/-/preview/
연합은 하나 존재하고, 연합의 인구는 (50 + 30 + 20 + 40) 이다. 연합의 크기가 4이기 때문에, 각 칸의 인구수는 140/4 = 35명이 되어야 한다.
https://upload.acmicpc.net/78951cb1-213d-416b-a64d-fb80697af36a/-/preview/
나의 풀이(정답 참고)
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
import sys
from collections import deque
def BFS(visited,x,y,my_map,N,L,R):
visited[x][y]=True
dx=[-1,1,0,0]
dy=[0,0,-1,1]
queue=deque()
queue.append((x,y))
countries=[(x,y)]
while queue:
v=queue.popleft()
for i in range(4):
mx=v[0]+dx[i]
my=v[1]+dy[i]
if 0<=mx<N and 0<=my<N and not visited[mx][my] and L<=abs(my_map[v[0]][v[1]]-my_map[mx][my])<=R:
visited[mx][my]=True
queue.append((mx,my))
countries.append((mx,my))
return countries
input=sys.stdin.readline
N,L,R=map(int,input().strip().split())
my_map=[]
for _ in range(N):
my_map.append(list(map(int,input().strip().split())))
count=0
while True:
is_ok=True
visited=[[False]*N for _ in range(N)]
for i in range(N):
for j in range(N):
if not visited[i][j]:
sum_country=BFS(visited,i,j,my_map,N,L,R)
if len(sum_country)>1:
tmp_sum=0
is_ok=False
for c1 in sum_country:
tmp_sum+=my_map[c1[0]][c1[1]]
for c2 in sum_country:
my_map[c2[0]][c2[1]]=tmp_sum//len(sum_country)
if is_ok:
break
count+=1
print(count)
- 위 문제는 BFS로 풀어야 한다. 문제를 봤을 때, 맵 형태가 나오면 BFS/DFS를 잘 못 떠올리는 경향이 있다. 위와 같이 dx, dy를 선언하여 탐색하는 방법이 있다는 것을 항상 기억하자
- visited여부를 보고, 방문하지 않았으면 해당 위치부터 BFS탐색을 시작한다. 만약 그 주위의 국가와의 차이가 L과 R사이에 존재한다면, countries에 담는다. 그 후, countries에 담긴 모든 국가의 인구수를 평균내고 해당 국가에 넣어준다.
- 아직 방문하지 않은 국가들을 모두 방문한 뒤 위 과정을 반복해주고, 맵의 모든 국가를 방문하였다면, 인구 이동이 한번 발생한 것이므로
count+=1을 해준다.