인구 이동 - 백준 #16234, 골드5, 구현/그래프/너비우선탐색/시뮬레이션

문제 링크

16234번: 인구 이동

풀이

from collections import deque

# 주어진 나라들에서 연합 찾기
def find_union(board, n, l, r):
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    groups = []
    visited = [[False for _ in range(n)] for _ in range(n)]
    
    # 모든 나라 순회, 연합 찾기
    for x in range(n):
        for y in range(n):
            if visited[x][y]:
                continue

            # (열위치, 행위치)
            new_group = [(x, y)]

            q = deque()
            q.append((x, y))
            visited[x][y] = True
            while q:
                cx, cy = q.popleft()
                for i in range(4):
                    nx = cx + dx[i]
                    ny = cy + dy[i]
                    if not (0 <= nx < n and 0 <= ny < n):
                        continue
                    if visited[nx][ny]:
                        continue
                    if not l <= abs(board[cx][cy] - board[nx][ny]) <= r:
                        continue
                    visited[nx][ny] = True
                    q.append((nx, ny))
                    new_group.append((nx, ny))

            groups.append(new_group)

    return groups

# 찾은 연합들의 인구 분배
def set_population(board, groups):
    # 연합 순회, 각 연합 인구 분배
    for group in groups:
        population_of_group = [board[a][b] for a, b in group]
        population_of_united = sum(population_of_group) // len(population_of_group)
        for x, y in group:
            board[x][y] = population_of_united


# 입력 받고, 인구 이동 시뮬레이션하여 결과 출력
def solution():
    n, l, r = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(n)]

    day = 0
    while True:
        # 연합을 찾아서, 연합이 더이상 생기지 않을 때까지 인구 분배 과정 반복
        groups = find_union(board, n, l, r)
        if not any(map(lambda x: len(x) > 1, groups)):
            break

        day += 1    # 인구 이동 횟수 누적
        set_population(board, groups)

    print(day)

if __name__ == "__main__":
    solution()