백준 16234 인구 이동 (파이썬)

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

16234번: 인구 이동

1. bfs로 이동하면서 인구수와 연합한 나라의 수, 좌표를 각각 people, cnt, move_q에 저장한다

2. 인구수 차이가 l과 r사이인 나라를 방문할 수 있는만큼 방문한다

3. move_q에서 좌표를 하나씩 불러와서 총 인구 수를 총 나라 수로 나눈 값으로 바꾼다

4. 연합한 나라의 수가 1이면 0, 아니면 1 반환을 해서 연합을 했는지 안했는지 알려준다

5. 위의 과정을 방문하지 않은 모든 나라에 대해서 bfs로 검사한다.

   bfs return값을 모두 더했을때 0이면 더 이상 연합할 수 없다는 뜻이므로 while문을 나와 연합한 횟수를 출력 

from collections import deque
import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(x, y):
    move_q = deque()
    q.append([x, y])
    c[x][y] = 1
    people, cnt = 0, 0
    while q:
        x, y = q.popleft()
        move_q.append([x, y])
        people += a[x][y]
        cnt += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not c[nx][ny]:
                if l <= abs(a[x][y] - a[nx][ny]) <= r:
                    c[nx][ny] = cnt
                    q.append([nx, ny])

    while move_q:
        x, y = move_q.popleft()
        a[x][y] = people // cnt

    if cnt == 1:
        return 0
    return 1

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

ans = 0
while True:
    q = deque()
    c = [[0]*n for _ in range(n)]
    cnt = 0
    for i in range(n):
        for j in range(n):
            if not c[i][j]:
                cnt += bfs(i, j)
    if not cnt:
        break
    ans += 1

print(ans)