[파이썬/Python] 백준 16234(🥇4): 인구 이동

숨·2025년 8월 9일

코테

알고리즘 문제 풀이

목록 보기

108/128

📌 문제 : 백준 16234

📌 문제 탐색하기

N : 땅의 가로 세로 크기 ( $1 ≤ N ≤ 50$ )
L, R : 인구수 제한 ( $1 ≤ L ≤ R ≤ 100$ )

문제 풀이

N×N 크기의 땅은 1×1 크기의 칸으로 나누어져 있다.
각 땅엔 1개의 나라가 있고 그 나라가 (r,c)에 있을 때 인구는 A[r][c]이다.
인접한 나라 사이엔 국경선이 있기 때문에 모든 국경선은 정사각형이다.
이 때, 조건에 따라 더 이상 인구 이동이 일어나지 않을 때까지 이동을 한다면 며칠이 걸리는지 구하는 문제이다.

인구 이동이 필요 없을 때까지 일어난다는 점에서 특정 조건까지 반복해야 하며, 인접 나라를 확인해야 하므로 BFS를 활용하고자 했다.

인접 나라는 상하좌우에 있기에 4가지 방향을 정의한다.
지나친 곳은 다시 방문하지 않으므로 방문한 곳을 저장해야 한다 → 방문 리스트 정의 필요!

BFS 이용

BFS 탐색 조건은 다음과 같이 정의한다.

N×N 범위 내
방문한 적 없는 나라
연합 가능 여부 확인
- 인구수 차이 확인 : L명 이상, R명 이하
- 연합 가능하면 연합 리스트에 추가하고 거기서 BFS 반복

인구 이동 반복문

인구 이동이 더 이상 필요 없을 때까지 이동을 반복해야 한다.

이동 조건 : 국경선이 열려 있어 이동 가능한 경우 → 즉, 연합 ⭕️
땅 전체를 방문 처리하면서 BFS 확인
- BFS 결과로 연합이 생기면 인구수 계산해 갱신
전체를 BFS한 후 연합이 하나도 없다면 반복문 종료
- 아니라면 날짜 추가 후 다시 수행

가능한 시간복잡도

while문 내 이중 for문 $N×N$ → $O(N^2)$
BFS문 → $O(N^2)$

최종 시간복잡도
최악일 때 $O(N^4) = O(50^4) = O(6,250,000)$ 이 되는데 이는 제한시간 2초 내 충분히 수행 가능하다.

알고리즘 선택

BFS로 인접 나라 확인해 조건에 맞는 연합 탐색
BFS 후 연합이 하나도 없을 때까지 전체 땅 탐색 반복

📌 코드 설계하기

BFS 구현
1-1. 연합 리스트 정의
1-2. 4방향 탐색하면서 범위 초과하지 않고 방문한 적 없으며 이동 가능한 위치 이동해 탐색 반복
1-3. 인접한 나라에서 인구차 확인해 연합 리스트에 추가
입력받기
정답 저장 변수 초기화
인접 방향 정의
인구 이동 필요 없을 때까지 반복
5-1. 방문리스트 정의
5-2. 연합 유무 확인
5-3. 땅 전체를 돌면서 BFS 수행해 연합 국가 얻기
5-4. 연합 있으면 인구수 계산해 갱신
5-5. 연합 없으면 정답 출력
5-6. 인구 이동 필요하면 정답 1 추가 후 반복

📌 시도 회차 수정 사항

1회차

TypeError: unsupported operand type(s) for -: 'str' and 'str'
나라 인구수를 입력받을 때 int형으로 받지 않아서 발생한 문제였다.
A = [list(input()) for _ in range(N)]를 수정했다.

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline


# bfs 구현
def bfs(x, y):
    queue = deque([(x, y)])
    # 연합 저장
    union = [(x, y)]

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

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            # 범위 내 방문 여부 확인
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                # 인구 차이 확인
                if L <= abs(A[x][y] - A[nx][ny]) <= R:
                    visited[nx][ny] = 1
                    queue.append((nx, ny))
                    union.append((nx, ny))
    return union


# 입력 받기
N, L, R = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

# 정답 초기화
answer = 0

# 인접 방향 확인
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

# 인구 이동 필요 없을 때까지 반복
while True:
    # 방문 리스트 정의
    visited = [[0 for _ in range(N)] for _ in range(N)]
    # 연합 유무 확인
    union_flag = 0
    # bfs 수행
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                visited[i][j] = 1
                union = bfs(i, j)

                # 연합 있으면 인구수 분배
                if len(union) > 1:
                    union_flag = 1
                    population = sum(A[x][y] for x, y in union) // len(union)
                    # 인구수 갱신
                    for x, y in union:
                        A[x][y] = population
    # 연합 없으면 인구 이동 종료
    if union_flag == 0:
        print(answer)
        break
    # 아니면 날짜 추가 후 계속 반복
    answer += 1

결과

✏️ 회고

이 문제의 경우 인접 나라 중 연합에 들어올 수 있는 나라 판단, 연합 유무, 연합 있을 때 인구 수 확인, 인구수 갱신, 그 후 다시 반복 등 다양한 조건들이 많았다. 조건이 많아지니 코드를 어떻게 짜야할 지 더 감이 안오는 것 같다. 난이도가 있는 문제들을 많이 접해서 조건을 만드는데 더 익숙해지도록 해야 겠다.