[BFS] 백준#16234: 인구 이동/Python

📝 문제

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

16234번: 인구 이동

💡 접근법

BFS 알고리즘과 큐(Queue) 자료구조를 활용하여 문제를 해결하였습니다. 문제해결 절차는 다음과 같습니다. 모든 국가를 대상으로 각각 중심국으로 선정하고, 상하좌우 방면에 연합이 가능한 인접국이 있는지 탐색하니다. 만일 연합국이 성립된다면, 해당 인접국을 중심으로 다시 상하좌우 방면의 인접국과 연합국이 성립되는지 여부를 확인합니다. 이 과정은 상하좌우 방면으로 연합국이 성립하지 않을 때까지 반복하고, 한 국가를 시작으로 가능한 모든 연합국을 찾을 때마다 \(1\)일씩 카운팅합니다.

💻 코드

1) 전체 코드

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

def bfs(x, y):
    q = deque()
    q.append((x, y))
    union_contry = []
    union_contry.append((x, y))
    while q:
        x, y = q.popleft()
        for dx, dy in d:
            nx = x + dx
            ny = y + dy
            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
                    q.append((nx, ny))
                    union_contry.append((nx, ny))
    return union_contry

if __name__ == '__main__':
    N, L, R = map(int, input().split())
    d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    graph = [[0]*N for _ in range(N)]

    for i in range(N):
        data = list(map(int, input().split()))
        for j in range(N):
            graph[i][j] = data[j]

    answer = 0
    while True:
        visited = [[False]*N for _ in range(N)]
        move = False
        for i in range(N):
            for j in range(N):
                if not visited[i][j]:
                    visited[i][j] = True
                    union_contry = bfs(i, j)
                    if 1 < len(union_contry):
                        move = True
                        population = sum([graph[x][y] for x, y in union_contry]) // len(union_contry)
                        for x, y in union_contry:
                            graph[x][y] = population

        # 모든 나라를 탐색했지만 인구 이동이 일어나지 않은 경우 무한 루프 탈출
        if not move:
            break
        # 인구 이동이 일어났기 때문에 1일 추가
        else:
            answer += 1
    print(answer)

2) 해설

(1) 패키지 import

import sys; input = sys.stdin.readline

파이썬 내장함수인 input보다 빠르게 값을 입력받기 위해 sys.stdin.readline을 사용하였습니다.

from collections import deque

큐(queue) 자료구조를 사용하기 위해 deque 모듈을 불러왔습니다.

(2) 메인 함수

if __name__ == '__main__':
    N, L, R = map(int, input().split())
    d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    graph = [[0]*N for _ in range(N)]

    for i in range(N):
        data = list(map(int, input().split()))
        for j in range(N):
            graph[i][j] = data[j]

    answer = 0
    while True:
        visited = [[False]*N for _ in range(N)]
        move = False
        for i in range(N):
            for j in range(N):
                if not visited[i][j]:
                    visited[i][j] = True
                    union_contry = bfs(i, j)
                    if 1 < len(union_contry):
                        move = True
                        population = sum([graph[x][y] for x, y in union_contry]) // len(union_contry)
                        for x, y in union_contry:
                            graph[x][y] = population

        # 모든 나라를 탐색했지만 인구 이동이 일어나지 않은 경우 무한 루프 탈출
        if not move:
            break
        # 인구 이동이 일어났기 때문에 1일 추가
        else:
            answer += 1
    print(answer)

탐색하지 않은 모든 국가를 대상으로, 하나의 국가씩 중심국으로 선정하고 가능한 모든 인접국을 찾는 과정을 반복합니다. 만일, 모든 국가를 탐색했고 더 이상 인접국이 없어 인구이동이 없다면(i.e., move == False), 무한 루프를 탈출하고 정답을 출력합니다.

(3) BFS: 인접국 탐색 함수

def bfs(x, y):
    q = deque()
    q.append((x, y))
    union_contry = []
    union_contry.append((x, y))
    while q:
        x, y = q.popleft()
        for dx, dy in d:
            nx = x + dx
            ny = y + dy
            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
                    q.append((nx, ny))
                    union_contry.append((nx, ny))
    return union_contry

중심국을 중심으로 상하좌우 방면의 인접국과 연합이 가능한지 탐색하는 함수입니다. 만일 연합국 성립이 가능하다면, 해당 인접국이 중심국이 됩니다. 이 국가로부터 다시 상하좌우 방면의 인접국을 찾을 때까지 탐색을 계속 이어갑니다. 만일 추가적인 연합국이 없다면, 지금껏 성립한 연합국 정보를 리턴합니다.

✅ 채점 결과

정답 확인

💾 Github

https://github.com/park-gb/algorithm-problem-solving/blob/main/dfs-bfs/boj_16234.py

GitHub - park-gb/algorithm-problem-solving: 알고리즘 문제 풀이 및 정리

📚 참고할 만한 포스팅

문제 풀이에 사용한 BFS 알고리즘과 큐 자료구조에 대한 자세한 설명은 아래 포스팅을 참고해 주세요.

https://heytech.tistory.com/56

[알고리즘] 너비 우선 탐색(BFS) 알고리즘에 대해 알아보자!(+Python 구현)

https://heytech.tistory.com/54

큐(Queue) 자료구조 이해(+ Python)

---

포스팅 내용에 오류가 있거나 접근법 및 코드 관련 피드백 환영합니다!😄
아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다 :)
고맙습니다.