16234: 인구 이동

• bfs 탐색을 하면서 연합의 국가 수(count)와 총 인구수(total), 그리고 해당 국가들의 좌표(coor)를 구해야함
  -> visit 리스트로 중복 제거를 하면서 2중 for문을 돌며 bfs 탐색
  -> count가 1보다 큰 경우 연합이 있는 경우이므로 [count, total, coor]를 state 리스트에 append해줌
• state 리스트가 비어있는 경우 연합이 존재하지 않는 경우이므로 break
• state 리스트의 길이만큼 for문을 돌며, world를 문제의 조건에 맞게 갱신해줌
• while문을 한 번 반복할 때마다 result += 1

import sys
from collections import deque

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

def bfs(a, b):
    global count, total
    queue = deque([])
    queue.append([a, b])
    visit[a][b] = True
    coor.add((a, b))

    result = []
    while queue:
        x, y = queue.popleft()
        count += 1; total += world[x][y]
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if L <= abs(world[x][y] - world[nx][ny]) <= R and not visit[nx][ny]:
                    visit[nx][ny] = True
                    queue.append([nx, ny])
                    coor.add((nx, ny))


N, L, R = map(int, sys.stdin.readline()[:-1].split())
world = []
for n in range(N):
    world.append(list(map(int, sys.stdin.readline()[:-1].split())))

result = 0
while True:
    visit = [[False for _ in range(N)] for _ in range(N)]
    state = []
    for i in range(N):
        for j in range(N):
            if not visit[i][j]:
                count = 0; total = 0; coor = set()
                bfs(i, j)
                if count > 1:
                    state.append([count, total, coor])

    if len(state) == 0:
        break
    else:
        for _ in range(len(state)):
            tmp = state[_][1] // state[_][0]
            for i in range(N):
                for j in range(N):
                    if (i, j) in state[_][2]:
                        world[i][j] = tmp

    result += 1
print(result)