백준 16234 python [인구 이동]

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

from collections import deque
import math

# with open ('./data.txt', 'r') as file:
#     lines = file.read().strip().split("\n")

# N, L, R = map(int, lines[0].split(" "))
N, L, R = map(int, input().split(" "))

moveX = [1, 0, -1, 0]
moveY = [0, -1, 0, 1]
start = True
temp = []
graph = []
day = 0

for i in range(N):
    # arr = list(map(int, lines[i+1].split(" ")))
    arr = list(map(int, input().split(" ")))
    graph.append(arr)
        

def bfs(x, y):
    Q = deque()
    Q.append((x, y))
    visited[y][x] = True
    union = []
    union.append((x, y))
    
    while Q:
        nowX, nowY = Q.popleft()
        
        for i in range(4):
            nX = nowX + moveX[i]
            nY = nowY + moveY[i]
            
            if(nX >= N or nX < 0 or nY >= N or nY < 0):
                continue
            
            if(visited[nY][nX]):
                continue
            
            a = abs(graph[nowY][nowX] - graph[nY][nX])
            
            if(L <= a and a <= R):
                visited[nY][nX] = True
                Q.append((nX, nY))
                union.append((nX, nY))

    if(len(union) <= 1):
        return 0

    result = math.floor(sum(graph[d][c] for c, d in union) / len(union))

    for c, d in union:
        graph[d][c] = result

    return 1

while start:
    visited = [[False] * N for _ in range(N)]
    temp = 0

    for y in range(N):
        for x in range(N):
            if(visited[y][x] == False):
                temp += bfs(x, y)

    if(temp == 0):
        start = False
        break
    
    day += 1

print(day)

이중 for 반복문 즉 전체 그래프 탐색을 계속 반복해야 하기 때문에 while문을 밖에다 돌려줘야지 생각했다.

그리고 연결이 끝난 시점에 평균을 구해서 값을 변경해줘야 하는데 어디서 해줄까 머리가 막혔었는데 다른 블로그를
살짝 참고해서 아이디어를 얻었다. ㅎㅎㅎ

bfs 함수 안에서 while문이 종료되는 시점에 해주면 된다.
연결이 끊겨서 더이상 인구이동을 할 수가 없다는 뜻이기 때문에.

아무튼 전체 그래프 탐색을 계속 반복하면서 날짜를 구하는게 핵심 포인트였던 것 같다.