16234 - 인구 이동

다음은 테스트케이스 4번을 대상으로 시각화한 것이다.

1. 첫번째 인구 이동

2. 두번째 인구 이동

3. 더 이상 인구이동 불가!

from collections import deque

N, L, R = map(int, input().split())
graph = []
for _ in range(N):
    temp = list(map(int, input().split()))
    graph.append(temp)
    
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]  
result = 0

def bfs(ox, oy, curNum):
    global union, L, R, graph
    # 연결되어있는 영역을 모아둔 리스트
    connectedList =[]
    connectedList.append((ox, oy))
    
    # 경계를 확장 할 수 있는 영역들이 q에 들어오면서 최대 어디까지 뻗어갈 수 있는지 확인
    q = deque()
    q.append((ox, oy))
    
    # 같은 경계 안의 영역인지 표시
    union[ox][oy] = curNum
    
    # 총 인구 수
    totalPeopleSum = graph[ox][oy]
    
    # 인구 이동이 가능한 영역의 개수
    totalPeopleCnt = 1
    
    while q:
        x, y = q.popleft()
        # 동/서/남/북 방향으로 모두 확인
        for n in range(4):
            nx = x + dx[n]; ny = y + dy[n]
            if 0<=nx<N and 0<=ny<N and union[nx][ny] == -1:
                if L <= abs(graph[x][y] - graph[nx][ny])<=R:
                    q.append((nx, ny))
                    union[nx][ny] = curNum
                    totalPeopleSum += graph[nx][ny]
                    totalPeopleCnt += 1
                    connectedList.append((nx, ny))
                    
    # 현재 ox,oy 영역과 인구 이동이 가능한 영역은 모두 평균 인구 값으로 갱신
    for r, c in connectedList:
        graph[r][c] = totalPeopleSum // totalPeopleCnt  
    return

# 더 이상 인구 이동이 없을 때 까지 반복
while True:
    union = [[-1]*N for _ in range(N)]
    curNum = 0
    for i in range(N):
        for j in range(N):
            if union[i][j] == -1:
                bfs(i, j, curNum)
                curNum += 1
              
    # 모든 인구의 이동이 끝난 경우 == 모든 인구가 한 경계에 들어오는 경우
    if curNum == N*N:
        break
    result += 1
    
print(result)