BFS&DFS_심화21) 인구이동 _ python

문제링크

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

16234번: 인구 이동

코드

# 인구이동 - bfs
from collections import deque
n, l , r = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

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

def bfs(x, y):
    union = [(x, y)]
    que = deque([(x, y)])
    visited[x][y] = True
    total_population = graph[x][y]
    while que:
        x, y = que.popleft()
        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(graph[x][y] - graph[nx][ny]) <= r:
                    visited[nx][ny] = True
                    que.append((nx, ny))
                    union.append((nx, ny))
                    total_population += graph[nx][ny]
    if len(union) > 1:
        new_population = total_population // len(union)
        for x, y in union:
            graph[x][y] = new_population
        return True
    return False
days = 0
while True:
    visited = [[False] * n for _ in range(n)]
    moved = False
    for i in range(n):
        for j in range(n):
            if not visited[i][j] and bfs(i, j):
                moved = True
    if not moved:
        break
    days += 1
print(days)