[백준] 16234번 인구 이동 파이썬 풀이

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

---

1. 풀이

• 모든 국가를 방문하면서 너비 우선 탐색(bfs)로 연합을 확인하자

핑크색은 연합이다.

N x N 크기의 땅에는 1개 이상의 연합이 존재할 수 있다. 즉, 위 그림처럼 그래프가 여러 개 존재할 수 있다는 것이다. 따라서 땅을 한 칸, 한 칸 방문해서 해당 국가가 이루는 연합 정보를 알아내야 한다.

이때 어떠한 연합에 포함된 국가는, 이전 bfs 과정에서 방문했었다는 의미이다. 따라서 재방문을 방지하기 위해 visited 리스트로 각 칸의 방문 여부를 표시하자.

 

 

• bfs 과정에서 연합 국가들의 정보를 저장해두자

연합 국가들의 인구 수를 조정해야 하므로, bfs 과정에서 방문한 국가(= 연합 국가)는 union 리스트 변수에 저장해야 한다. bfs가 끝나면, union 내 모든 국가를 방문해서 새 인구수를 할당한다.

만약 union 리스트에 오직 1개의 국가만 포함된다면, 해당 국가는 인근 국가와 국경선이 열려 있지 않다는 의미이다.

 

 

• 종료 조건은 모든 국가를 방문하면서 누적한 bfs의 반환 값이 0일 때이다

bfs 메서드에서 union 리스트 길이가 1이면 0을 반환하고, 2 이상이면 1을 반환하게끔 만들자. 그러면 모든 국가를 방문하면서 누적한 bfs 반환 값, 즉 연합의 개수가 0일 때 더 이상의 인구 이동이 발생하지 않았다는 것이므로, 그대로 프로그램을 종료하면 된다.

 

 

 

2. 정답 코드

from collections import deque
import sys

input = sys.stdin.readline


def validate_coordinate(r, c):
    return True if 0 <= r < N and 0 <= c < N else False


def bfs(r, c):
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    queue = deque([(r, c)])
    visited[r][c] = True
    union = []
    population = 0
    count = 0

    while queue:
        x, y = queue.popleft()
        union.append((x, y))
        population += maps[x][y]
        count += 1

        for d in directions:
            dx, dy = x + d[0], y + d[1]

            if not validate_coordinate(dx, dy) or visited[dx][dy]:
                continue

            if L <= abs(maps[x][y] - maps[dx][dy]) <= R:
                queue.append((dx, dy))
                visited[dx][dy] = True

    new_population = population // count
    for country in union:
        maps[country[0]][country[1]] = new_population
    return 1 if count > 1 else 0  # count == 1은 연합 구성 X


N, L, R = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(N)]

answer = 0
while True:
    visited = [[False] * N for _ in range(N)]
    result = 0
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                result += bfs(i, j)
    if result == 0:
        print(answer)
        break
    answer += 1