6. [re] 인구 이동

백준

1. BFS

import sys
from collections import deque
input = sys.stdin.readline
n, l, r = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

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

def bfs(x, y, index):
    united = []
    united.append((x, y))
    q = deque()
    q.append((x, y))
    union[x][y] = index #현재 연합 번호
    s = board[x][y]
    count = 1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and union[nx][ny] == -1:
                if l <= abs(board[nx][ny] - board[x][y]) <= r:
                    q.append((nx, ny))
                    union[nx][ny] = index
                    s += board[nx][ny]
                    count += 1
                    united.append((nx, ny))

    for i, j in united:
        board[i][j] = s // count

total = 0
while True:
    union = [[-1] * n for _ in range(n)]
    index = 0
    for i in range(n):
        for j in range(n):
            if union[i][j] == -1:
                bfs(i, j, index)
                index += 1
    if index == n * n:
        break
    total += 1

print(total)