[Python] 백준 16234번 - 인구 이동 (골드 4)

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 구현
 - 시뮬레이션
 - BFS

 

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

16234번: 인구 이동

 

문제

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

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

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

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

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

입력

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

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

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

출력

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

 

 

---

 

 

해당 문제를 풀기 위해 몇가지 고려해야 할 부분이 있다.

 

1. 한번에 하나의 연합만이 발생하는 것이 아니다. 즉, N=4일 때 (16개 나라) 8개의 연합이 생길 수 있음

2. 각 나라 인구수의 합과 연합이 된 나라의 개수를 관리해야한다.

3. 연합을 찾은 후 인구 이동이 발생한 결괏값(평균)은 한 번에 바뀌어야 한다. 즉, 연합을 찾고 같은 알고리즘으로 또 반복을 하면 시간초과가 발생한다.

 

이러한 부분을 나는 어떻게 접근해야 하는지 깨닫지 못하였고, 이는 집합으로 해결하여 중복 좌표를 고려하지 않는 해결법이다.

 

import sys
input = sys.stdin.readline

N, L, R = map(int, input().split())

data = []

for _ in range(N):
    data.append(list(map(int, input().split())))
    
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

result = 0

from collections import deque

def bfs(x, y):
    global flag
    visited = set()
    
    value = 0 # 인구수 총 합
    cnt = 0 # 나라 수
    
    q = deque()
    q.append((x, y))
    visited.add((x, y))
    total_visited.add((x, y))
    while q:
        x, y = q.popleft()
        value += data[x][y]
        cnt += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and (nx, ny) not in visited:
                if L <= abs(data[x][y] - data[nx][ny]) <= R:
                    flag = True # 한 번이라도 인구 이동이 있으면 True
                    q.append((nx, ny))
                    visited.add((nx, ny))
                    total_visited.add((nx, ny))
                    
    return value // cnt, visited

while True:
    flag = False
    total_visited = set() # 방문한 좌표, 중복을 방지하기 위해 set으로
    unions = [] # 평균 값, 좌표들 목록
    
    for i in range(N):
        for j in range(N):
            if (i, j) not in total_visited: # 방문한 적이 없으면 bfs
                avg, visited = bfs(i, j)
                unions.append((avg, visited)) # 평균, 좌표들
   
    for value, union in unions: # 연합에 속한 나라들의 인구 이동 평균값을 한번에 해결.(다시 bfs를 하지 않아도 됨)
        for x, y in union:
            data[x][y] = value   
            
    if flag:
        result += 1
    else:
        print(result)
        break

 

조금 더 생각했더라면 풀 수 있지 않았을까? 싶지만 집합을 떠올리지 못했기 때문에 아마 어려웠을 것 같다.