구현, BFS - 16234번: 인구 이동

from collections import deque

line = list(map(int, input().split()))
n, l, r = line[0], line[1], line[2]

maps = []
cnt_days = 0

for i in range(0, n):
    lines = list(map(int, input().split()))
    maps.append(lines)

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

# -------


def bfs(i, j, union, daily_visited):
    # 오늘 재분배한 나라에 추가
    queue = deque([(i, j)])
    union.add((i, j))
    daily_visited.add((i, j))

    while queue:
        x, y = queue.popleft()

        for k in range(0, 4):
            nx, ny = x + dx[k], y + dy[k]
            # 현재 나라의 상하좌우 중 맵 내에 있는 나라이고, 방문하지 않은 나라라면 (union 안에 존재하지 않는 걸로 체크하면 안됨! 전체에 대해서 방문 유무를 봐야 함)
            if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in daily_visited:
                # 인구 수 차이 계산(절댓값)
                diff = abs(maps[x][y] - maps[nx][ny])

                # 인구 수 차이가 L이상 R이하라면 서로 연결
                if l <= diff <= r:
                    queue.append((nx, ny))
                    union.add((nx, ny))
                    daily_visited.add((nx, ny))

    # 더 갈 곳 없으면 현재까지 방문한 애들 인구수 재분배 (연합의 길이가 2 이상인 경우만)
    if len(union) > 1:
        total = 0
        for u in union:
            total += maps[u[0]][u[1]]
        # 각 나라 당 재분배된 인구 수
        per_country = int(total / len(union))
        for u in union:
            maps[u[0]][u[1]] = per_country

    return


# --------------------
while True:
    # 전체 맵 탐색
    daily_visited = set()  # 오늘 방문한 나라 초기화

    moved = False  # 오늘 인구 이동 유무

    for i in range(0, n):
        for j in range(0, n):
            if (i, j) not in daily_visited:
                union = set()
                bfs(i, j, union, daily_visited)

                # 연합이 2이상이었다면 인구 이동
                if len(union) > 1:
                    moved = True

    # 오늘 인구 이동이 없었다면 종료
    if not moved:
        break
    # 인구 이동 있었다면 카운트
    cnt_days += 1

print(cnt_days)