[백준][Python] 16234번 인구 이동 - BFS

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

16234번: 인구 이동

 

from collections import deque
import sys
input = sys.stdin.readline
dx = [0,0,1,-1]
dy = [1,-1,0,0]

N, L, R = map(int, input().split())
arr = [ list(map(int, input().split())) for _ in range(N) ]
if N == 1:
    print(0)
    sys.exit(0)

answer = 0


nextTurn = True

while nextTurn: 
    nextTurn = False
    visit = [[False]*N for _ in range(N)]
    road = []

    for i in range(N):
        for j in range(N):
            if visit[i][j]:
                continue
                
            q = deque([(i,j)])
            visit[i][j] = True
            total = arr[i][j]
            road.append([(i,j)])
            while q:
                x, y = q.popleft()

                for t in range(4):
                    nx = x + dx[t]
                    ny = y + dy[t]
                    if 0<=nx<N and 0<=ny<N:
                        if not visit[nx][ny] and L <= abs(arr[nx][ny]-arr[x][y]) <= R:
                            visit[nx][ny] = True
                            q.append((nx,ny))
                            total += arr[nx][ny]
                            road[-1].append((nx,ny))
                
            if len(road[-1]) > 1:
                road[-1].append(total // len(road[-1]))
                nextTurn = True
                #print(road)
            else:
                visit[i][j] = False


    if nextTurn:
        answer += 1
        for r in road:
            people = r.pop()
            for x, y in r:
                arr[x][y] = people
        #print(arr)
        #del road : 시간초과 유발범

print(answer)

 

 

 

풀이 과정

여러군데에서 시작되는 경우에 곧바로 arr에 업데이트하면 최근 값이 세팅되어 잘못 계산된다

그래서 한 번 진행될 때마다 road 리스트에 한 줄씩 추가하며 진행했다

arr.copy()를 안 쓰려고 그랬다