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

📖  문제

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

16234번: 인구 이동

 

💻  코드

 

import sys
from collections import deque


def bfs(y, x, checked, m, N, L, R):
    # 연합을 이루고 있는 나라들 위치 저장
    u = [(y, x)]
    # BFS
    q = deque()
    q.append((y, x))
    checked[y][x] = 1
    dy, dx = (1, -1, 0, 0), (0, 0, 1, -1)
    while q:
        y, x = q.popleft()
        for d in range(4):
            ny, nx = y + dy[d], x + dx[d]
            if 0 <= ny < N and 0 <= nx < N and checked[ny][nx] == 0 and L <= abs(m[ny][nx] - m[y][x]) <= R:
                checked[ny][nx] = 1
                q.append((ny, nx))
                u.append((ny, nx))
    # 연합된 나라들에 대한 인구 이동 실시
    p = sum(m[y][x] for y, x in u) // len(u)
    for y, x in u:
        m[y][x] = p


def move(m, N, L, R):
    # 중복 체크를 막기 위한 자료구조
    checked = [[0 for _ in range(N)] for _ in range(N)]
    # 체크 횟수 카운트
    cnt = 0
    # 이중 for문
    for y in range(N):
        for x in range(N):
            # 만약 아직 체크되지 않았다면
            if checked[y][x] == 0:
                # 체크 횟수 + 1
                cnt += 1
                # 해당 좌표에 대해 bfs
                bfs(y, x, checked, m, N, L, R)
    # 만약 인구 이동이 없었다면
    if cnt == N * N:
        return False
    # 인구 이동이 있었다면
    else:
        return True


def solution():
    N, L, R = map(int, sys.stdin.readline().strip().split())
    m = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]
    res = 0
    # 인구 이동이 더이상 발생하지 않을 때까지 move 반복 호출
    while move(m, N, L, R):
        res += 1
    print(res)


solution()

 

 

🙌  한마디

배울 것이 많은 문제였다. 처음 문제를 봤을 때는 어떻게 풀지 감이 잡히지 않았다. BFS로 접근해야했으나 단순 구현으로 알고리즘을 작성하였고 결국 예외 케이스들이 꼬리에 꼬리를 물고 발생하며 이렇게 풀어서는 요구사항을 만족하는 완전한 로직을 구현할 수 없겠다는 것을 깨달았다.

알고 보니 BFS 문제였다. 왜 BFS라는 것을 인지하지 못했을까 고민해봤는데, 지금까지 풀었던 BFS 문제들은 큐 시작점 하나에 대해 BFS를 한번만 수행했었는데, 해당 문제는 BFS를 이중 for문을 돌리며 여러번 수행해야했었다. 그래서 올바른 방향의 풀이를 생각해내지 못했던 것 같다. BFS를 이용하니 생각보다 빠르게 문제가 풀렸다.