[Python] 백준 16234번 인구 이동

[Python] 백준 16234번 인구 이동

안녕하세요 :-D

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

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가 낯선 분들은 아래의 링크를 참고하세요!

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

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

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

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

from http://wisdom-990629.tistory.com/72 by ccl(A) rewrite - 2021-08-14 00:00:49