[파이썬] [구현] 백준 16234 인구 이동

문제

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

16234번: 인구 이동

 

코드

from collections import deque
queue=deque()

n,left,right=map(int, input().split())

graph=[list(map(int, input().split())) for _ in range(n)]

dx=[-1,1,0,0]
dy=[0,0,-1,1]

def bfs(r,c):
    global flag
    visited[r][c]=True
    sum_array.append(graph[r][c])
    sum_index.append((r,c))
    queue.append((r,c))
    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:
                if visited[nx][ny]==False and left<=abs(graph[nx][ny]-graph[x][y])<=right:
                    flag=True
                    visited[nx][ny]=True
                    sum_array.append(graph[nx][ny])
                    sum_index.append((nx, ny))
                    queue.append((nx,ny))

result=0
while True:
    visited=[[False]*n for _ in range(n)]
    sum_array=[]
    sum_index=[]
    flag=False
    for i in range(n):
        for j in range(n):
            if visited[i][j]==False:
                bfs(i,j)
                ave=sum(sum_array)//len(sum_array)
                for ii,jj in sum_index:
                    graph[ii][jj]=ave
                sum_array = []
                sum_index = []
    if flag==False:
        break
    result+=1

print(result)