(백준) 16234 인구 이동 (BFS) - Python

16234번: 인구이동

N×N사이즈의 땅이 있고, 땅은 1×1개의 구획으로 나누어져 있다.

각각의 토지에는 나라가 하나씩 존재하고, r행c열에 있는 나라에는 A(r)(c)인이 살고 있다.

인접한 국가 사이에는 국경선이 있습니다.

모

www.acmicpc.net

– 문제 설명

N*N 사이즈의 땅이 있고, 각 칸은 각각의 나라이며, 나라마다 사람이 살고 있습니다.
L, R을 입력하고 각 구획의 국가와 인접한 국가의 인구수의 차이가 L 이상 R 이하인 경우, 하루 동안 국경이 열린다.
땅에서 열리는 국경이 모두 열리면 인구 이동을 한다.
인구는 인접한 토지에서 국경이 열린 국가들이 균등하게 이동한다.

(소수점은 버림)
며칠이 지나면 인구 이동이 불가능해졌는지 확인합니다.

– 입출력 예

인구 이동 코스

국경이 열리고 인구를 재분배한다.
하루 이동한 결과, 모든 나라의 인구가 35로 L, R=(20이상 50이하)로 인구수가 공제하는 나라가 없기 때문에 탐색을 종료한다.

– 접근

인접한 국가들이 조건에 따라 국경이 열리므로 BFS 방식을 사용해야 한다고 생각했다.
하루 동안 모든 국가의 인구이동이 끝나고 새롭게 반복을 시작할 때마다 방문배열을 초기화시킨다.
반복을 진행한다 어느 날, 인구의 이동이 하나도 없는 경우는 반복을 종료한다.

– 코드

import sys
from collections import deque
input = sys.stdin.readline

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

def bfs(i, j):
    global fail
    dq = deque()        # 너비우선탐색을 위한 큐
    dq.append((i, j))   # 현재위치 추가
    country = ((i, j))        # 국경 개방가능한 이웃 나라들을 추가
    visited(i)(j) = 1         # 현재 위치 방문체크
    rlt_sum = area(i)(j)      # 개방한 나라들의 총 인구

    while dq:
        x, y = dq.popleft()     # 큐에서 제일 앞 원소 꺼냄
        for d in range(4):
            nr, nc = x + dr(d), y + dc(d)
            # 4방향 탐색한 위치가 유효범위이고 방문한 적이 없다면
            if 0 <= nr < n and 0 <= nc < n and not visited(nr)(nc):
                # 또한 그 나라와 현재 나라의 인구수 차이가 l 이상 r 이하라면
                if l <= abs(area(nr)(nc) - area(x)(y)) <= r:
                    dq.append((nr, nc))         # 큐에 추가
                    country.append((nr, nc))    # 국경 개방한 나라 리스트에 추가
                    rlt_sum += area(nr)(nc)     # 총 인구수에 개방한 나라 인구 더해줌
                    visited(nr)(nc) = 1         # 방문처리
    # 현재 위치 주변에 국경 개방한 나라가 있다면
    if len(country) > 1:
        fail = 1    # 탐색 성공
    # 개방한 나라들의 인구를 분배
    for x, y in country:
        area(x)(y) = rlt_sum // len(country)

# 땅의 넓이 n, 유효 범위 l, r 입력
n, l, r = map(int, input().split())
area = (list(map(int, input().split())) for _ in range(n))
ans = 0

while True:
    fail = 0    # 0이면 실패, 1이면 성공으로 설정
    visited = ((0) * n for _ in range(n))   # 방문탐색을 위한 배열 (반복마다 초기화)
    # 나라들을 한칸씩 순회하며 너비우선 탐색
    # 다른칸에서 너비우선 탐색할때 방문했다면 탐색X
    for i in range(n):
        for j in range(n):
            if not visited(i)(j):
                bfs(i, j)   # 너비우선탐색
    # 탐색에 실패했다면 반복종료
    if fail == 0:
        break
    # 탐색 성공했다면 결과에 +1
    # 인구 이동이 끝난 상태로 다시 반복시작
    ans += 1

print(ans)

시간 초과로 실패할까 걱정했지만 성공했다.

재귀를 사용하는 것은 어렵고 DFS나 백트래킹 방식으로 해결하는 것을 피할 수 있습니다.

DFS, 백트래킹으로 문제를 해결하는 것도 연습할 필요가 있는 것 같다.

(백준) 16234 인구 이동 (BFS) – Python

– 문제 설명

– 입출력 예

인기글

– 접근

– 코드