인구 이동

p.353

 

python3로 하니까 시간초과

pypy3로 함

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

n,l,r=map(int, input().split())
A=[]
for i in range(n):
  A.append(list(map(int, input().split())))

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

day_cnt=0 # day count

while True: # 더이상 연합이 만들어지지 않을 때까지
  uni_flag=0 # 연합이 만들어졌는지 체크
  day_visit=[[0]*n for _ in range(n)] # 방문한 나라 체크 (하루마다 초기화)

  for i in range(n):
    for j in range(n):  # 한 나라씩 돌며
      if day_visit[i][j]==0: # 오늘 그 나라에 방문한 적이 없다면
        queue=deque()
        uni=[] # 연합 국가 
        people_sum=0 # 연합 국가 총 인구수

        queue.append((i,j))
        day_visit[i][j]=1
        uni.append((i,j))
        people_sum+=A[i][j]

        while queue: # 연합할 수 있는 국가가 없을때까지
          x,y=queue.popleft()
          
          for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]
            if nx>=0 and ny>=0 and nx<n and ny<n: # 맵 범위 안
              if day_visit[nx][ny]==0 and (abs(A[x][y]-A[nx][ny])<=r) and (abs(A[x][y]-A[nx][ny])>=l): # 연합 조건에 만족하면
                queue.append((nx,ny))
                day_visit[nx][ny]=1
                uni.append((nx,ny))
                people_sum+=A[nx][ny]
                uni_flag=1
        
        uni_people=int(people_sum/len(uni))
        for ux,uy in uni:
          A[ux][uy]=uni_people

  if uni_flag==0: # 만들어진 연합이 없다.
    break
  else:
    day_cnt+=1

print(day_cnt)