백준: 16234 인구 이동

문제

16234번: 인구 이동

 

문제 풀이

 이전에 다룬 안전 영역, 단지번호붙이기 문제와 같이 `Floodfil`을 활용하여, 접근 가능한 영역을 판단하고 그에 따라 처리하는 문제이다. 이 문제에서는 방문 가능한 영역에 대한 조건과 방문 후에 기존 인구에 대한 처리 부분이 추가된 문제이다.

 

 현재 국가로부터 방문 가능한 인접 국가는 `L <= abs(현재 국가 - 인접 국가) <= R`이라는 조건을 만족하여야 한다. 만약 연합국이 1 이상 (현재 국가 제외)라면 인구의 수를 모든 `연합국가의 인구수의 합 / 연합국가의 수`로 변경하여야 한다. 이를 BFS를 통해 처리하면 문제를 쉽게 해결할 수 있다.

 

코드

from sys import stdin
from collections import deque


def visitable(x, y):
    return 0 <= x < n and 0 <= y < n and not visited[x][y]


def bfs(start):
    q = deque([start])
    cur_united = [start]

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

        for dx, dy in dirs:
            next_x, next_y = x + dx, y + dy

            if visitable(next_x, next_y) and \
                    l <= abs(populations[x][y] - populations[next_x][next_y]) <= r:
                visited[next_x][next_y] = True
                q.append((next_x, next_y))
                cur_united.append([next_x, next_y])

    # 탐색을 시작하는 국가는 포함하므로 1 이상인 경우 국경이 열린 상태.
    if len(cur_united) > 1:
        # 문제의 조건에 따라 새로운 인구 수를 계산함.
        new_population = sum(populations[x][y] for x, y in cur_united) // len(cur_united)
        for x, y in cur_united:
            populations[x][y] = new_population
        return 1

    return 0


if __name__ == '__main__':
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
    n, l, r = map(int, stdin.readline().split())
    populations = [list(map(int, stdin.readline().split())) for _ in range(n)]
    cnt = 0

    while True:
        visited = [[False] * n for _ in range(n)]
        num_of_united = 0

        for i in range(n):
            for j in range(n):
                if not visited[i][j]:
                    visited[i][j] = True
                    num_of_united += bfs([i, j])

        # 국경이 열리지 않는 다면, 더 이상 탐색을 진행하지 않아도 됨.
        if not num_of_united:
            break

        cnt += 1

    print(cnt)