[Python] 백준 16234번 인구 이동

 

안녕하세요 :-D

오늘은 백준 삼성 SW 역량 테스트 기출문제 중 하나인

16234번 인구 이동 문제를 풀어보았습니다.

 

백준 16234번

16234번: 인구 이동

이번 문제는 기존에 많이 풀었던 단순 구현과는 달리

생각해야 할 부분이 많은 문제였습니다.

저는 총 4단계에 걸쳐 해결해보았습니다!

---

1. 인구 이동 조건 확인하기

각 나라 사이에 국경을 개방할 수 있는지 여부를 확인합니다.

모든 나라를 기준으로 상, 하, 좌, 우를 살펴본 후

나라 간의 인구수 차이가 L 이상 R 이하라면 국경선을 열어야 합니다.

---

2. 국경선 열어 연합 목록 구하기

1번 조건을 만족한다면 각 국가의 국경선을 열어줍니다.

만약 국경선을 개방하게 된다면, 인접한 칸을 통해 다른 나라로 이동할 수 있습니다.

인접 리스트와 BFS를 통해 연합의 목록을 구해주었습니다.

따라서 인접 리스트를 통해 각각의 노드에서 (국경선이 개방되어) 인접한 국가의 목록을 표현하고,

BFS (너비 우선 탐색)를 통해 그래프를 탐색하였습니다.

---

3. 인구 이동

2번 과정을 통해 인접한 국가의 목록이 구해진다면 인구 이동을 실시합니다.

연합을 이루고 있는 국가들의 인구수를 모두 더한 후, 연합 국가의 수로 나누어줍니다.

이후 연합에 속한 국가의 인구수를 수정해줍니다.

마지막으로 인구 이동이 끝나면 연합을 해체해줍니다.

---

4. 반복

1 ~ 3의 과정은 더 이상 인구 이동이 일어날 수 없을 때까지 반복되어야 합니다.

저는 while 문을 통해 무한 반복을 하였고,

2번에서 연합 목록이 나오지 않은 경우를 종료 조건으로 설정하였습니다.

또한 while 문이 한 번씩 반복될 때마다 인구 이동 날짜를 증가시켰습니다.

---

아래는 해당 과정을 바탕으로 제가 구현한 코드입니다.

from collections import deque
n, l, r = map(int, input().split())
popularity = [list(map(int, input().split())) for _ in range(n)]
day = 0
graph = dict()

def check(value, input, x, y): # 인구 이동 조건 확인
    if (input >= l) and (input <= r):
        value.append((x, y))

def border(i, j): 
    value = []
    if i-1 >= 0:
        top = abs(popularity[i-1][j]-popularity[i][j])      
        check(value, top, i-1, j)
    if i+1 < n:
        bottom = abs(popularity[i+1][j]-popularity[i][j])
        check(value, bottom, i+1, j)
    if j-1 >= 0:
        left = abs(popularity[i][j-1]-popularity[i][j])
        check(value, left, i, j-1)
    if j+1 < n:
        right = abs(popularity[i][j+1]-popularity[i][j])
        check(value, right, i, j+1)
    if value:
        graph[(i, j)] = value

def bfs(start): 
    visit = list()
    queue = deque()
    queue.append(start)
    while queue:
        enqueue = queue.popleft()
        if enqueue not in visit:
            visit.append(enqueue)
            queue.extend(graph[enqueue])
    return visit

while True:
    # 인접 그래프 그리기
    for i in range(n):
        for j in range(n):
            border(i, j)

    # 종료 조건
    if not graph: 
        break
	
    # 인구 이동
    while graph:
        movement = bfs(list(graph.keys())[0])
        sum = 0
        # 연합 인구수 조정
        for move in movement:
            sum += popularity[move[0]][move[1]]
        result = int(sum/len(movement))
        for move in movement:
            popularity[move[0]][move[1]] = result
            del(graph[move]) # 연합 해체
    day += 1

print(day)

border 함수와 check 함수를 통해 1번 과정을,

bfs 함수를 통해 2번 과정을 구현하였습니다.

저는 해당 과정에서 python deque의 큐 기능을 사용하였습니다.

참고로 deque의 경우에는 큐 외에도 스택으로 사용할 수 있습니다.

deque가 낯선 분들은 아래의 링크를 참고하세요!

collections — 컨테이너 데이터형 — Python 3.9.6 문서

 

마지막으로 3번 과정을 통해 인구 수를 수정, 연합을 해체하고

위의 과정을 반복해주었습니다. (4번 과정)

반복의 경우에는 border 함수를 통해 인접 리스트 (graph)를 구하고,

값이 존재하지 않는다면 이를 종료합니다.