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

문제 링크:

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

16234번: 인구 이동

 

이 문제는 "이것이 코딩 테스트다" 책 유형별 기출문제 21번에 해당한다.

---

풀이 유형:

구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 시물레이션

 

★문제풀이 Point★

1. 모든 나라의 위치에서 상, 하, 좌, 우로 국경선을 열 수 있는지 확인(bfs)

2. 같은 연합끼리 인구를 동일하게 분배

 

풀이 과정:

이 문제는 각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하는 문제로, 전형적인 DFS/BFS 유형의 문제이다.

모든 나라의 위치에서 상, 하, 좌, 우로 국경선을 열 수 있는지 bfs방식으로 확인한다.

국경선을 열 수 있다면 연합에 추가하고, 인구 이동 처리를 진행하면 된다.

 

 

풀이 코드:

다음 코드는 PyPy3에서 실행해 맞았다.

이를  파이썬에서 풀면 80%에서 시간초과가 뜬다.

 

백준 16234번 채점 결과

 

# 16234번 인구 이동

from collections import deque

# 맵 크기와 인구 이동 가능한 수 입력 받기
n, l, r = map(int, input().split())

# 인구 데이터 입력 받기
graph = [list(map(int, input().split())) for _ in range(n)]

# 상, 하, 좌, 우 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


# 특정 위치에서 출발하여 모든 연합을 체크한 뒤에 데이터 갱신
def process(x, y, index):
    # (x, y) 위치와 연결된 연합 정보를 담는 리스트
    united = []
    united.append((x, y))
    # 너비 우선 탐색을 위한 큐 자료구조 정의
    q = deque()
    q.append((x, y))
    union[x][y] = index # 현재 연합 번호 할당
    summary = graph[x][y] # 현재 연합의 전체 인구 수
    count = 1 # 현재 연합의 국가 수
    # 큐가 빌때까지 반복(BFS)
    while q:
        x, y = q.popleft()
        # 현재 위치에서 4가지 방향을 확인하며
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 바로 옆에 있는 나라를 확인하며
            if 0 <= nx < n and 0 <= ny < n and union[nx][ny] == -1:
                # 옆에 있는 나라와 인구 차이가 L명 이상, R명 이하라면
                if l <= abs(graph[nx][ny] - graph[x][y]) <= r:
                    q.append((nx, ny))
                    # 연합에 추가
                    union[nx][ny] = index
                    summary += graph[nx][ny]
                    count += 1
                    united.append((nx, ny))
    # 연합 국가끼리 인구 분배
    for i, j in united:
        graph[i][j] = summary // count
    return count

total_count = 0

# 더 이상 인구 이동을 할 수 없을 때까지 반복
while True:
    union = [[-1] * n for _ in range(n)]
    index = 0
    for i in range(n):
        for j in range(n):
            if union[i][j] == -1:
                process(i, j, index)
                index += 1
    # 모든 인구 이동이 끝난 경우
    if index == n * n:
        break
    total_count += 1

# 인구 이동 횟수 출력
print(total_count)

 

 

 

16234 인구 이동