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

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

---

 

접근 방식

문제 읽으면서 적은 풀이 방법.. 근데 조금 다르게 풀었다

문제를 보면 인접한 나라들 사이의 인구수를 고려해서 탐색해야 한다고 나와있다. 여기서 그래프 문제라는 것을 파악했다.

이후에는 인접한 칸들 간의 인구수를 비교하고, 그게 조건에 부합하면 queue에 넣었다.

 

이때 주의해야 할 점이 한 번의 탐색이 끝난 후, 방문하지 않은 나라가 있을 경우 그 나라를 시작으로 또 탐색해야 한다. 왜냐면 그 나라를 기준으로 새로운 연합이 만들어질 수 있기 때문이다.(이때 이미 다른 연합에 포함된 나라는 고려하지 않는다.)

위 과정을 possible() 메서드와 bfs() 메서드를 엮어서 구현했다.

 

방문하지 않은 나라가 있을 경우 bfs()로 탐색을 시작하고, 만약 인구 이동이 일어나면 문제의 정답인 count를 +1 해주었다.

그러고 인구 이동을 할 때는 move() 메서드를 돌려서 분배시켜 주었다.

 

 

정답 코드

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

N, L, R = map(int, input().split())
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
count = 0

def move(union):
    union_sum = 0
    
    for x, y in union:
        union_sum += graph[x][y]

    return union_sum // len(union)


def bfs(a, b, visited):
    dq = deque([(a, b)])
    union = [(a, b)]
    visited[a][b] = True

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

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                if L <= abs(graph[x][y] - graph[nx][ny]) <= R:
                    visited[nx][ny] = True
                    dq.append((nx, ny))
                    union.append((nx, ny))

    moved = move(union)
    for x, y in union:
        graph[x][y] = moved

    return len(union) > 1  # 인구 이동이 발생하면 True, 아니면 False


def possible():
    global count
    visited = [[False] * N for _ in range(N)]
    movement = False

    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                if bfs(i, j, visited):
                    movement = True
    
    if movement:
        count += 1
    return movement


graph = [list(map(int, input().split())) for _ in range(N)]

while True:
    if not possible():
        break

print(count)