[acmicpc] 16234. 인구 이동(python)

---

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

N,L,R=map(int,input().split())
arr=[]
for _ in range(N):
    arr.append(list(map(int,input().split())))

dirs=[(1,0),(0,1),(-1,0),(0,-1)]
def bfs(row,col):
    visit[row][col]=1
    q=deque([(row,col)])
    total=0
    field=[]
    while q:
        r,c=q.popleft()
        field.append((r,c))
        total+=arr[r][c]
        for i in range(4):
            nr,nc=r+dirs[i][0],c+dirs[i][1]
            if 0>nr or nr>=N or 0>nc or nc>=N: continue
            if visit[nr][nc]==1: continue
            if L<=abs(arr[nr][nc]-arr[r][c])<=R: # 두나라의 인구차이 비교
                visit[nr][nc]=1
                q.append((nr,nc))
    
    # update될 국가가 2개 이상이 아닌 경우, 업데이트 없이 false 반환
    if len(field)<=1:
        return False
    for r,c in field:
        arr[r][c]=total//len(field)
    return True

count=0
while True:
    visit = [[0]*N for _ in range(N)]
    flag=0
    for r in range(N):
        for c in range(N):
            if visit[r][c]==0:
                if bfs(r,c): flag=1
    if flag==0: break # update된 국가가 없다면 종료
    count += 1
print(count)

 

---

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

16234번: 인구 이동