[백준/파이썬] 16234번 인구 이동

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

문제 해석

 

n * n 크기의 땅이 존재한다. 각 땅에는 인구수가 담겨 있다. 각 땅은 하나의 나라이다.

인구 이동이 시작되면 다음과 같은 과정이 일어난다.

• 인접한 나라, 즉 국경선을 공유하는 나라의 인구수 차이가 주어진 L이상 R이하라면 국경선이 열린다. 
• 같은날 모든 국경선을 열어준다.
• 국경선이 모두 열리면 인구 이동이 시작된다.
• 인구 이동은 국경선이 열린 영역의 모든 나라의 인구수의 평균이며 나머지는 버린다.
• 인구 이동이 완료되면 국경선은 닫히게 된다.
• 더 이상 인구 이동이 일어나지 않을 때 까지 며칠이 걸리는지 구하는 문제이다.

더 이상 인구 이동이 일어나지 않을 때 까지 며칠이 걸리는지 구하는 문제이다.

---

코드

 

from collections import deque
input = __import__('sys').stdin.readline

n, l, r = map(int, input().split())
arr = []
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
for _ in range(n):
    arr.append(list(map(int, input().split())))

def bfs(x, y):
    # 기본 세팅
    q = deque()
    q.append((x, y))
    visit[x][y] = 1
    _sum = arr[x][y]    # 인구 이동이 발생 시 나누어주기 위한 값
    near = [(x, y)]     # 인구 이동 발생될 나라들
    while q:
        i, j = q.popleft()
        for k in range(4):
            x, y = i + dx[k], j + dy[k]
            if not(0 <= x < n and 0 <= y < n): continue
            if visit[x][y] == 1: continue
            if l <= abs(arr[i][j] - arr[x][y]) <= r:    # 인구 이동 가능한 나라
                _sum += arr[x][y]   # 해당 나라의 인구를 더해주고
                visit[x][y] = 1
                q.append((x, y))
                near.append((x, y)) # 해당 나라를 추가
    
    change = _sum // len(near)  # 인구 이동 완료 후 값
    flag = False    # 값이 변경되었는지 저장하는 배열
    for x, y in near:
        if arr[x][y] != change: 
            flag = True # 변경된 값이 존재하면 True
        
    return flag, change, near

cnt = 0
while 1:
    flag = False
    visit = [[0] * n for _ in range(n)]
    temp = []   # 변경할 값 잠시 저장할 리스트
    for i in range(n):
        for j in range(n):
            f, c, near = bfs(i, j)
            if f: # 변경할 값이 존재한다면
                for x, y in near:   # temp에 변경할 값 추가
                    temp.append((x, y, c))  # 좌표, 변경할 값
                flag = True   # 값이 한번이라도 변경되면 True
    if not flag: break  # 값이 한번도 변경되지 않았으면 멈추기
    
    # 인구 이동 후 변경된 값 갱신
    for x, y, c in temp:
        arr[x][y] = c
    cnt += 1

print(cnt)

---

문제 풀이

 

BFS에서 국경선이 열릴 영역을 구한다. 영역을 구하면서 해당 영역에 존재하는 나라의 인구수의 총합과, 인접한 나라의 좌표를 구해준다.

이후 변경될 값이 존재하는지 확인해준다.

변경될 값이 존재하는지 bool값, 바꿀 값(인구수 평균), 바꿀 배열을 반환하도록 하였다.

 

실행 부분에서는 while문을 통해 반복해준다. flag를 설정하여 BFS를 통해 바뀐 값이 존재하지 않는다면 탈출하도록 한다.

바뀐 값이 존재한다면 바꿀 값과 좌표가 담긴 near 배열을 temp에 넣어준다.

 

모든 영역을 탐색한 뒤 변경할 값을 갱신해준다.

 

바뀐 값을 바로 적용하지 않고 모든 탐색이 완료된 뒤 변경해 주어야한다. 이를 실수해 첫 제출 때 틀렸다.

또한 파이썬에서는 시간초과가나 pypy로 제출하였다.. (코드 최적화가 필요할지도..)