[파이썬] 백준 알고리즘 No.16234 인구 이동

나의 코드

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

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


def bfs(a, b):
    queue = deque()
    queue.append((a, b))
    tmp = []
    tmp.append((a, b))

    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 not visited[nx][ny]:
                if l <= abs(graph[nx][ny] - graph[x][y]) <= r:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
                    tmp.append((nx, ny))
    return tmp

result = 0
while True:
    visited =[[False] * (n + 1) for _ in range(n + 1)]
    flag = 0
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                visited[i][j] = True
                cur = bfs(i, j)

                if len(cur) > 1:
                    flag = 1
                    people = sum(graph[x][y] for x, y in cur) // len(cur)
                    for x, y in cur:
                        graph[x][y] = people
    if flag == 0:
        break
    result += 1
print(result)

 

풀이 방법

bfs 후 해당 지역 값 리스트를 저장하여 평균을 냄

평균을 내다가 더이상 상태가 변하지 않는다면 종료