[Python] 백준(BOJ): 16234. 인구 이동

💁🏻  문제

16234번: 인구 이동

---

🤷🏼‍♀️  문제 설명

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

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

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

 

⚙️  풀이

"매 인구이동마다 생성되는 연합을 어떻게 구해낼 것인가?"에 대한 접근방법을 생각해내야 하는 문제였다.
주어진 조건에 따라 영역을 나누어 탐색하도록 DFS를 구현하면 된다. 

   1) 방문하지 않은 나라인 경우(if not visited[i][j]), DFS를 수행하여 국경선을 공유하는 연합 생성여부를 확인
   2) a. 연합이 생성된 경우, 인구 이동
       b. 연합이 생성되지 않은 경우, 더 이상 인구 이동을 할 수 없다는 의미이므로 종료
   3) 더 이상 연합이 생성되지 않을 때까지 while문 수행

문제를 보고 바로 접근법을 바로 파악할 수 있었다. 탐색문제 응용력이 조금 높아진 것 같기도
비슷한 유형으로는 프로그래머스: 무인도 여행 문제를 참고하면 좋을 것 같다.

import sys
from collections import Counter
sys.setrecursionlimit(10**6)

dx, dy = [1, 0, -1, 0], [0, -1, 0, 1]
N, L, R = map(int, sys.stdin.readline().split())
arr = []
for i in range(N):
    arr.append(list(map(int, sys.stdin.readline().split())))


def dfs(x, y, visited, arr):
    global u
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and L <= abs(arr[x][y] - arr[nx][ny]) <= R:
            visited[nx][ny] = 1
            u[(nx, ny)] = arr[nx][ny]
            dfs(nx, ny, visited, arr)


answer = 0
while True:
    visited = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    union = []
    for i in range(N):
        for j in range(N):
            if visited[i][j]:
                continue
            u = {(i, j): arr[i][j]}
            dfs(i, j, visited, arr)
            if len(u) > 1 and len(set(u.values())) > 1:
                union.append(u)
    if len(union) == 0:
        break
    for u in union:
        people = sum(u.values()) // len(u)
        for ui, uj in u:
            arr[ui][uj] = people
    answer += 1
print(answer)