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

문제 설명

 

입출력 예제

---

풀이 코드

1. 더 이상 인구 이동이 일어나지 않을 동안 bfs 탐색을 통해 연합을 이루는 나라들을 구한다.
2. 연합을 이루는 나라가 2개 이상이라면  연합인구수의 평균을 구해 인구이동을 시작한다.
3. 인구 이동이 없다면 반복문을 종료하고 인구 이동이 발생한 횟수를  출력한다.

 

정답 코드

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

n, l, r = map(int, input().split())

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

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

def bfs(x, y):
    q = deque()
    q.append((x, y))
    visited[x][y] = True
    union = [(x, y)]

    while q:
        x, y = q.popleft()

        for i in range(4):
            move = True
            nx = dx[i] + x
            ny = dy[i] + y

            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                if l <= abs(country[nx][ny] - country[x][y]) <= r:
                    q.append((nx, ny))
                    visited[nx][ny] = True
                    union.append((nx, ny))

    return union
    

while True:
    visited = [[False] * n for _ in range(n)]
    move = False

    for x in range(n):
        for y in range(n):
            if not visited[x][y]:
                union = bfs(x, y)
                
                if len(union) > 1:
                    move = True
                    population = sum(country[i][j] for i, j in union) // len(union)

                    for i, j in union:
                        country[i][j] = population

    if not move:
        break
    cnt += 1

print(cnt)