풀이

1. 하루하루를 기준으로 연합을 체크한다.
   

BFS로 탐색하면서, L이상 R이하인지를 확인하면서 따로 visited 했는지 체크해두면 연합별로 묶을 수 있다.

day=0
while True:
    for i in range(n):
        for j in range(n):
            if visited[i][j]==0:
                visited[i][j]=1
                bfs(i,j)
	day+=1

BFS 내부 함수에는 인접한 나라와의 인구 수 차이가 L과 R 사이인지 체크하고, 이미 방문한 국가인지 아닌지 체크한 다음 같은 영역에 있는 국가들의 (전체합)/국가 수 를 할당하면 된다.

queue=deque()
dx=[1,-1,0,0]
dy=[0,0,1,-1]
def bfs(x,y):
    queue.append((x,y))
    union=[(x,y)]
    while queue:
        cur_x,cur_y=queue.popleft()
        for i in range(4):
            next_x=cur_x+dx[i]
            next_y=cur_y+dy[i]
            if next_x>=n or next_x<0 or next_y>=n or next_y<0 or visited[next_x][next_y]==1:
                        continue
            if r>=abs(graph[next_x][next_y]-graph[cur_x][cur_y])>=l:
                  visited[next_x][next_y]=1
                  queue.append((next_x,next_y))
                  union.append((next_x,next_y))
    if len(union)<=1:
        return 0
    result=sum(graph[a][b] for a,b in union)//len(union)

    for a,b in union:
        graph[a][b]=result
    
    return 1

여기서 union(연합)이 감지되지 않는다면, 0을 return하게 하여, 추후에 인구 이동을 멈출 토글로 사용하게 한다.

아래는 전체 코드다.

# 16234 인구이동
from collections import deque
n,l,r=map(int,input().split())
graph=[list(map(int,input().split())) for _ in range(n)]
# 연합인지 체크하기

queue=deque()
dx=[1,-1,0,0]
dy=[0,0,1,-1]
def bfs(x,y):
    queue.append((x,y))
    union=[(x,y)]
    while queue:
        cur_x,cur_y=queue.popleft()
        for i in range(4):
            next_x=cur_x+dx[i]
            next_y=cur_y+dy[i]
            if next_x>=n or next_x<0 or next_y>=n or next_y<0 or visited[next_x][next_y]==1:
                        continue
            if r>=abs(graph[next_x][next_y]-graph[cur_x][cur_y])>=l:
                  visited[next_x][next_y]=1
                  queue.append((next_x,next_y))
                  union.append((next_x,next_y))
    if len(union)<=1:
        return 0
    result=sum(graph[a][b] for a,b in union)//len(union)

    for a,b in union:
        graph[a][b]=result
    
    return 1

day=0
while True:
    stop=0
    visited=[[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if visited[i][j]==0:
                visited[i][j]=1
                stop+=bfs(i,j)
            
    if stop==0:
        break
    day+=1
print(day)

Ref

https://velog.io/@seungjae/%EB%B0%B1%EC%A4%80-16234%EB%B2%88-%EC%9D%B8%EA%B5%AC-%EC%9D%B4%EB%8F%99-%EC%82%BC%EC%84%B1SW%EC%97%AD%EB%9F%89%ED%85%8C%EC%8A%A4%ED%8A%B8-Python