[Algorithm] 백준 16234 인구 이동 | 파이썬 BFS

※ 16234 인구 이동

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

문제 해결 TIP

모든 나라의 위치에서 BFS를 수행하여 인접한 나라의 인구수를 확인한 뒤에, 가능하다면 국경선을 열고 인구 이동 처리를 진행한다. visited 배열을 따로 두어 index를 확인하면서 더 이상 인구 이동을 할 수 없을 때까지 반복한다. BFS를 처리할 때 인구 분배를 같이 해나가는게 중요한 것 같다. 

 

전체 코드

from collections import deque

N, L, R = map(int,input().split())
graph = []
for i in range(N):
    graph.append(list(map(int,input().split())))
#graph = [[50, 30], [20, 40]]

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

def bfs(x,y,index):
    united = []
    united.append((x,y))
    queue = deque()
    queue.append((x,y))
    summary = graph[x][y]
    visited[x][y] = index
    count = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == -1:
                if L <= abs(graph[nx][ny] - graph[x][y]) <= R:
                    queue.append((nx, ny))
                    visited[nx][ny] = index
                    summary += graph[nx][ny]
                    count += 1
                    united.append((nx,ny))
    #연합 국가끼리 인구 분배
    for i,j in united:
        graph[i][j] = summary // count
    return count

total_count = 0
#더 이상 인구 이동을 할 수 없을 때까지 반복
while True:
    visited = [[-1]*N for _ in range(N)]
    index = 0
    for i in range(N):
        for j in range(N):
            if visited[i][j] == -1:
                bfs(i,j,index)
                index += 1
    #모든 인구 이동이 끝난 경우
    if index == N*N:
        break
    total_count += 1

print(total_count)