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

 

 

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

16234번: 인구 이동

 

 

 

 

 

✅ Solution

• bfs를 이용해서 모든 나라의 위치에서 국경선을 열 수 있는지 확인한다.
• 만약 열 수 있다면 연합에 추가하고 각 나라의 인구를 업데이트해 준다.
• 위 과정을 국경선을 열 수 있는 나라가 없을 때까지 반복한다.

 

 

 

 

 

✅ Code

import sys
input = sys.stdin.readline
from collections import deque

def bfs(x, y, visited):
    queue = deque() # 연합을 맺을 수 있는 나라 정보
    queue.append((x, y))

    union = [(x, y)] # 연합을 맺은 나라들
    visited[x][y] = True # 방문 처리
    union_summary = people[x][y] # 연합 맺은 나라의 인구 수의 합

    while queue:
        x, y = queue.popleft()

        for i in range(4): # 상하좌우 확인
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                if l <= abs(people[x][y] - people[nx][ny]) <= r: # 만약 국경을 열 수 있다면
                    queue.append((nx, ny)) 
                    visited[nx][ny] = True
                    union.append((nx, ny))
                    union_summary += people[nx][ny]

    if len(union) == 1:
        return False 

    for x, y in union: # 인구 이동
        people[x][y] = union_summary // len(union)

    return True



n, l, r = map(int, input().split())
people = [list(map(int, input().split())) for _ in range(n)]
answer = 0

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while True:
    visited = [[False] * n for _ in range(n)] # 나라를 모두 방문했는지 확인
    stop = True

    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                if bfs(i, j, visited): # 인구 이동을 했다면 계속 진행
                    stop = False

    if stop:
        break
    else:
        answer += 1

print(answer)