[정글 베이직 23] BFS(너비 우선 탐색)

BFS는 그래프 탐색의 가장 기본이 되는 방법 중 하나입니다. 시작점에서 가까운 정점부터 층별로 방문한다는 점이 핵심입니다.

BFS란?

BFS(Breadth-First Search)는 가까운 정점부터 차례대로 탐색하는 방식입니다. 그래서 흔히 "너비 우선 탐색"이라고 부릅니다.

핵심 자료구조

큐(Queue)

예제 그래프

0 ─── 1
│       │
└ 2 ── 3

시작 정점

0에서 시작한다고 가정합니다.

BFS가 큐를 쓰는 이유

큐는 먼저 들어온 데이터가 먼저 나가는 구조입니다. 따라서 시작점 근처에서 발견한 정점들을 순서대로 처리할 수 있어, 자연스럽게 가까운 정점부터 탐색하게 됩니다.

탐색 과정을 단계별로 보기

초기 상태

visited = [0]

queue = [0]

0을 꺼냄

0과 연결된 정점은 1, 2입니다.

visited = [0, 1, 2]

queue = [1, 2]

1을 꺼냄

1과 연결된 정점 0, 2는 이미 방문했습니다.

visited = [0, 1, 2]

queue = [2]

2를 꺼냄

2와 연결된 정점 중 아직 방문하지 않은 3을 새로 방문합니다.

visited = [0, 1, 2, 3]

queue = [3]

3을 꺼냄

더 이상 새로 방문할 정점이 없습니다.

최종 결과 = [0, 1, 2, 3]

한눈에 보는 BFS 순서표

단계	현재 정점	새로 방문한 정점	방문 결과
1	0	1, 2	[0, 1, 2]
2	1	없음	[0, 1, 2]
3	2	3	[0, 1, 2, 3]
4	3	없음	[0, 1, 2, 3]

풀이 핵심

시작 정점을 큐에 넣고, 큐에서 하나씩 꺼내면서 인접한 정점 중 아직 방문하지 않은 정점을 다시 큐에 넣습니다. 이 과정을 큐가 빌 때까지 반복하면 됩니다.

정답 코드

from collections import deque

def bfs(graph, start):
    """
    너비 우선 탐색
    """
    visited = [start]
    queue = deque([start])

    while queue:
        current = queue.popleft()

        for next_node in graph[current]:
            if next_node not in visited:
                visited.append(next_node)
                queue.append(next_node)

    return visited

# 테스트 케이스
if __name__ == "__main__":
    graph = {
        0: [1, 2],
        1: [0, 2],
        2: [0, 1, 3],
        3: [2]
    }

    print("=== BFS (너비 우선 탐색) ===")
    result = bfs(graph, 0)
    print(f"시작 정점: 0")
    print(f"방문 순서: {result}")

주의할 점

방문 체크를 하지 않으면 이미 본 정점을 또 큐에 넣게 됩니다. 따라서 BFS에서는 visited 관리가 필수입니다.