[백준/Python] 16234 인구 이동

문제 링크

16234번: 인구 이동

 

문제 풀이

• 현재 국가 위치에서 상하좌우의 국가의 인구수 차이를 계산하고, 하나라도 그 차이가 l이상 r이하일 때, 두 국가는 문이 열려 있으므로 인구 이동을 하게 된다.
• 인접한 국가 사이 중 문이 열려 있는 국가를 대상으로 반복 탐색한 후 해당 국가 전체에 대해 인구 이동을 시작한다.
• (1,1) 위치부터 (n,n) 위치까지의 국가에 대해서 인구 이동이 모두 진행되었다면, 또다시 (1,1) 위치부터 인접 국가와의 인구수 차이를 계산하여 더 이상 l이상 r이하의 차이가 나오지 않을 때까지 진행하면 된다.

 

전체 코드

import sys
from collections import deque
input = sys.stdin.readline

# 인구 이동을 하게되는 국가들
def mig(x, y):
    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()
        visited[x][y] = True
        location.append((x, y))
        country.append(popul[x][y])
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                if l <= abs(popul[x][y] - popul[nx][ny]) <= r:
                    visited[nx][ny] = True
                    queue.append((nx, ny))

# 인구 이동 후의 각 나라의 바뀐 인구 수
def check():
    total = sum(country) // len(country)
    for x, y in location:
        popul[x][y] = total

n, l, r = map(int, input().split())
popul = [list(map(int, input().split())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

day = 0
while True:
    visited = [[False] * n for _ in range(n)]
    move = False # 인구 이동이 발생하지 않음
    for i in range(n):
        for j in range(n):
            country = [] # 인구 이동이 발생하는 국가의 인구 수
            location = [] # 인구 이동이 발생하는 국가 위치
            if not visited[i][j]:
                mig(i, j)
                # 인구 이동이 발생했을 때
                if len(country) > 1:
                    check()
                    move = True # 인구 이동이 발생함
    if move == False:
        break
    else:
        day += 1

print(day)