[백준 16234] 인구 이동 (python)

16234번: 인구 이동

---

BFS를 이용하여 인접한 칸과의 차이가 L이상 R이하인지 확인하자! 시간초과가 나서 PyPy3으로 제출하였다.

 

1. 방문여부를 확인하는 visited배열을 생성한다.
2. arr[i][j]를 돌면서 인구 이동을 할 칸들을 저장할 trans배열을 생성한다.
3. 4방향으로 차이가 L이상 R이하 인것이 있다면 queue와 trans배열에 저장하고 방문 체크, flag, _sum을 update한다.
4. 인구이동이 일어난다면(trans > 1) 각 칸을 _sum // len(trans)로 update한다.
5. 인구 이동이 있었다면(flag) result 를 1 올려주고, 없다면 break해준다.

 

import sys
from collections import deque
input = sys.stdin.readline
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
N, L, R = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))

trans = []
result = 0

while True:
    flag = False
    visited = [[False]*(N) for _ in range(N)]

    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                queue = deque([[i, j]])
                visited[i][j] = True
                _sum = arr[i][j]
                trans = [[i, j]]

                while queue:
                    x, y = queue.popleft()
                    for k in range(4):
                        nx = x+dx[k]
                        ny = y+dy[k]
                        if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                            if L <= abs(arr[x][y]-arr[nx][ny]) <= R:
                                visited[nx][ny] = True
                                queue.append([nx, ny])
                                trans.append([nx, ny])
                                _sum += arr[nx][ny]

                # 인구이동이 있었다면 
                if len(trans) > 1:
                    flag = True
                    for x, y in trans:
                        arr[x][y] = _sum//len(trans)
                        
    if flag:
        result += 1
    else:
        break

print(result)