[백준 16234] 인구 이동

문제 보기

백준에 이 문제는 따로 알고리즘 분류가 없지만, 나는 BFS로 푼 문제이다.

두 나라의 인구가 이동하는 조건은 다음과 같다.

위에 해당하는 단계들이 1번의 인구이동이다.

여기서 실수할 수 있는 부분이 있다.

나는 문제를 풀 때, 한 개의 연합국에서 인구이동이 끝날 때 1번의 인구이동이라고 카운트를 세었지만, 정답은 주어진 맵에서 가능한 모든 연합국들의 인구이동이 끝나는 것이 1번의 인구이동이었다.

따라서 문제를 해결하기 위한 로직은 다음과 같다.

1. 주어진 맵의 각 위치마다 BFS를 진행한다. 이 때, 한 번의 인구이동동안 연합국에 해당하는지 확인하기 위한 집합 변수(unions)를 둔다. (11번째 줄)

2. 연합국이 아닌 모든 나라들에 대해서 BFS를 진행한다. (12~33번째 줄)

3. 한 번의 BFS가 끝났을 때, 연합을 이루는 나라가 있다면 인구이동을 하고, 연합국 집합에 추가한다. (34~40번째 줄)

4. 인구이동이 일어났다면 카운트를 센다. (41~44번째 줄)

여담이지만, 파이썬과 같은 집합자료형이 없는 언어라면 disjoin-set(서로소 집합)을 써야할 것 같다.

import sys
from collections import deque
 
n, L, R = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for c in range(n)]
 
answer = 0
directions = ((-1, 0), (0, 1), (1, 0), (0, -1))
while True:
    moved = False
    unions = set()
    # BFS
    for r in range(n):
        for c in range(n):
            if (r, c) not in unions:
                q = deque([(r, c)])
                visited = set([(r, c)])
                
                total, count = 0, 0
                while q:
                    cur_r, cur_c = q.pop()
                    total += board[cur_r][cur_c]
                    count += 1
                    
                    for dr, dc in directions:
                        next_r = cur_r + dr
                        next_c = cur_c + dc
                        if 0 <= next_r < n and 0 <= next_c < n:
                            if (next_r, next_c) not in visited and (next_r, next_c) not in unions:
                                # set a union
                                if L <= abs(board[cur_r][cur_c] - board[next_r][next_c]) <= R:
                                    q.appendleft((next_r, next_c))
                                    visited.add((next_r, next_c))
                # migration
                if count > 1:
                    result = total // count
                    for row, col in visited:
                        board[row][col] = result
                    unions |= visited
                    moved = True
    if moved:
        answer += 1
    else:
        break
print(answer)