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

 

16234번: 인구 이동

 

- 문제 설명

• 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, 백트래킹으로 문제를 푸는 것도 연습할 필요가 있을 것 같다.