백준 16234 python 풀이

차근 차근 백준 문제 풀이를 업로드 해볼 생각이다. 주 목적은 구현 실력 늘리기..? 그래서 주로 문제 카테고리가 구현이 될 것 같다. 아무튼 첫번째 문제는
16234번 인구 이동 문제이다. 골드 5에 해당하고, 구현+bfs 정도가 쓰인 것 같다.

1. 문제

https://www.acmicpc.net/problem/16234
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
  국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

2. 입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

3. 풀이

우선 어렵지는 않았는데, 국경을 여는 것과 인구 이동의 순서가 헷갈렸던 것 같다. 이 부분에서 생각이 꼬이면, 아마 못 풀 가능성이 높은 문제 같다.

나는 다음과 같은 사고 과정을 거쳐서 풀게 되었다.

0. while문을 돌면서 조건이 맞을 때까지(인구 이동이 일어나지 않을 때까지) 무한 반복
1. 일단 (0, 0) 인덱스에서 (n-1, n-1)인덱스까지 순회한다
2. 각 인덱스마다 bfs를 수행한다 -> 최대로 연결 되어 있는 나라들의 모음을 찾기 위해
3. 이 때, 서로 연결된 나라들의 모음이 존재하지 않으면, 인구 이동이 일어나지 않으니까 while문을 빠져나간다
4. 서로 연결 되어 있는 나라들의 모음을 담은 리스트를 순회하면서 인구 이동을 시켜주고 days를 +1해준다
5. 1-4를 반복한다

일단 이게 내 사고과정이었다는 것이고.. 말로는 이해가 잘 안될 것 같으니 소스코드를 보자

4. 소스코드

# 16234 인구 이동 (골드 5)

from collections import deque
import sys
dy = [1, -1, 0, 0]
dx = [0, 0, -1, 1]

# bfs를 이용해서, 연결되어 있는 모든 나라를 찾음
def bfs(q):
    global visited, n, r, l, a, temp, sum_people
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < n:
                if visited[ny][nx] == 0:
                    if l <= abs(a[y][x]-a[ny][nx]) <= r:
                        visited[ny][nx] = 1
                        temp.append([ny, nx])
                        q.append([ny, nx])
                        sum_people += a[ny][nx]
    
# 입력
n, l, r = map(int, input().split())
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))

# 해결
days = 0
while True:
    visited = [[0]*n for _ in range(n)]
    q = deque()
    opened_nations = []

    # 나라들을 순회하면서, bfs로 가능한 연결되어있는 모든 나라들의 조합을 구해서
    # opened_nations에 인구수와 함께 넣는다
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0:
                temp = []
                sum_people = a[i][j]
                visited[i][j] = 1
                temp.append([i, j])
                q.append([i, j])
                bfs(q)
                if 1 < len(temp):
                    opened_nations.append((temp, sum_people))
    
    # 만약 국경이 열려있지 않으면 인구이동이 일어나지 않는 것이니까 break
    if len(opened_nations) == 0:
        break
    
    # 인구 이동
    for nations, peoples in opened_nations:
        cnt_people = peoples // len(nations)
        for y, x in nations:
            a[y][x] = cnt_people
    
    days += 1
    # 문제 조건에서 반복이 2000회 이상 수행되지 않는다고 했으니까
    # 2000이 넘어가면 코드가 이상하다는 것을 알려주고 stop
    if 2000 < days:
        print("something error!")
        sys.exit()

print(days)

5. 분석

딱히 문제 자체가 어려운 것도 아니었고, bfs만 알면 풀 수 있었지만 중간에 생각이 꼬일 염려가 있으니 조심해서 풀 것. 주석 처리 잘해서 꼬이지 않게 하기. 최대한 함수로 처리할 건 함수화 하여 처리하기.

6. 결과