CS학습2026년 8월 24일

BFS: 큐(Queue)로 구현하는 레벨 단위 그래프 탐색

너비 우선 탐색(BFS)은 시작 정점에서 가까운 노드부터 차례로 방문하는 그래프 탐색 알고리즘이다. 큐(Queue)의 선입선출(FIFO) 특성을 이용해 레벨(depth) 단위로 탐색을 진행하며, 가중치가 없는 그래프에서 최단 경로를 보장한다. 웹 크롤러의 링크 탐색, 소셜 네트워크의 친구 추천, 네트워크 라우팅 등 실무에서 폭넓게 쓰인다.

송민성6분 읽기

1. 개념

너비 우선 탐색(BFS, Breadth-First Search)은 그래프나 트리에서 시작 정점으로부터 가까운 노드를 먼저 방문하고, 그다음 단계로 멀리 있는 노드를 순차적으로 방문하는 탐색 알고리즘이다.

핵심은 "레벨(level) 단위 확장"이다. 시작 노드를 레벨 0이라고 하면, 시작 노드와 직접 연결된 노드들이 레벨 1, 그 노드들과 연결된 아직 방문하지 않은 노드들이 레벨 2가 된다. BFS는 레벨 0을 모두 처리한 뒤 레벨 1로, 레벨 1을 모두 처리한 뒤 레벨 2로 넘어가는 방식으로 동작한다.

이 순서를 관리하기 위해 큐(Queue) 자료구조를 사용한다. 큐는 선입선출(FIFO, First In First Out) 구조이므로 먼저 발견된 노드가 먼저 처리되고, 그 결과 자연스럽게 가까운 노드부터 순서대로 방문하게 된다.

깊이 우선 탐색(DFS, Depth-First Search)과 비교하면 차이가 명확하다. DFS는 후입선출(LIFO)인 스택(Stack)이나 재귀 호출 스택을 이용해 한 방향으로 끝까지 파고드는 반면, BFS는 넓게 퍼지듯이 탐색한다.

2. 왜 사용하는가

가중치가 없는 그래프(unweighted graph)에서 두 노드 사이의 최단 경로를 찾을 때 BFS는 정답을 보장한다. 레벨 단위로 확장하기 때문에 목표 노드를 처음 방문하는 순간이 곧 최단 거리이기 때문이다.

DFS로도 그래프 전체를 탐색할 수 있지만, 최단 경로를 구하려면 모든 경로를 탐색한 뒤 비교해야 해서 비효율적이다. BFS는 목표 노드를 발견하는 즉시 탐색을 중단해도 최단 경로가 보장되므로 목적에 맞다.

또한 BFS는 "특정 거리 이내의 모든 노드 찾기", "연결 요소(connected component) 판별", "이분 그래프(bipartite graph) 검사" 같은 문제에도 자연스럽게 적용된다.

3. 동작 원리

시작 노드를 큐에 넣고 방문 처리한다.
큐가 빌 때까지 다음을 반복한다.

- 큐에서 노드를 하나 꺼낸다(dequeue). - 꺼낸 노드의 인접 노드들을 확인한다. - 방문하지 않은 인접 노드는 방문 처리하고 큐에 넣는다(enqueue).

큐가 비면 탐색이 끝난다.

방문 처리를 큐에 넣는 시점에 하는 이유가 중요하다. 꺼낼 때 방문 처리를 하면 같은 노드가 큐에 중복으로 들어가 불필요한 연산이 늘어난다. 넣는 시점에 방문 처리를 해야 각 노드가 큐에 정확히 한 번만 들어간다.

4. 코드 예제

기본적인 BFS 구현과, 최단 경로(거리)를 함께 구하는 버전이다.

python

from collections import deque

def bfs(graph: dict[str, list[str]], start: str) -> list[str]:
    """방문 순서를 반환하는 기본 BFS"""
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()  # 큐에서 꺼내기: O(1)
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)      # 넣는 시점에 방문 처리
                queue.append(neighbor)

    return order


def bfs_shortest_distance(graph: dict[str, list[str]], start: str) -> dict[str, int]:
    """시작 노드로부터 각 노드까지의 최단 거리(간선 수)를 반환"""
    distance = {start: 0}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in distance:
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)

    return distance


if __name__ == "__main__":
    graph = {
        "A": ["B", "C"],
        "B": ["A", "D", "E"],
        "C": ["A", "F"],
        "D": ["B"],
        "E": ["B", "F"],
        "F": ["C", "E"],
    }

    print(bfs(graph, "A"))
    # ['A', 'B', 'C', 'D', 'E', 'F']

    print(bfs_shortest_distance(graph, "A"))
    # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2}

경로 자체를 복원하고 싶다면 부모 노드를 기록해두면 된다.

python

from collections import deque

def bfs_shortest_path(graph: dict[str, list[str]], start: str, target: str) -> list[str] | None:
    """시작 노드에서 목표 노드까지의 최단 경로를 반환"""
    if start == target:
        return [start]

    visited = {start}
    queue = deque([start])
    parent = {start: None}

    while queue:
        node = queue.popleft()

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node

                if neighbor == target:
                    # 경로 복원: target에서 시작점까지 거슬러 올라간다
                    path = [target]
                    while parent[path[-1]] is not None:
                        path.append(parent[path[-1]])
                    return path[::-1]

                queue.append(neighbor)

    return None  # 도달 불가능


graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

print(bfs_shortest_path(graph, "A", "F"))
# ['A', 'C', 'F']

5. 시간 복잡도 또는 성능 특성

시간 복잡도: O(V + E) — V는 정점(vertex) 개수, E는 간선(edge) 개수. 모든 정점을 한 번씩 큐에 넣고 꺼내며, 모든 간선을 한 번씩 확인하기 때문이다.
공간 복잡도: O(V) — 방문 여부 기록과 큐에 최악의 경우 모든 정점이 들어갈 수 있다.
큐의 enqueue/dequeue는 각각 O(1)이다(collections.deque 기준). 파이썬 리스트를 큐 대신 사용하면 pop(0)이 O(N)이라 전체 성능이 O(V²)로 나빠지므로 반드시 deque를 써야 한다.
인접 리스트(adjacency list)로 그래프를 표현했을 때 위 복잡도가 성립한다. 인접 행렬(adjacency matrix)을 쓰면 인접 노드를 찾는 데 O(V)가 걸려 전체가 O(V²)가 된다.

6. 실무 사용 사례

웹 크롤러(web crawler): 시작 페이지에서 링크를 따라가며 페이지를 수집할 때, 얕은 depth의 페이지부터 균등하게 수집하고 싶다면 BFS를 사용한다.
소셜 네트워크 추천: "친구의 친구" 같은 N촌 관계를 찾을 때, 거리(촌수)를 기준으로 탐색해야 하므로 BFS가 적합하다.
네트워크 라우팅: 홉(hop) 수가 최소인 경로를 찾는 문제는 간선 가중치가 모두 1인 최단 경로 문제와 같다.
게임 맵 탐색: 격자(grid) 기반 맵에서 두 지점 사이 최소 이동 횟수를 구할 때(미로 찾기 등) 자주 쓰인다.
가비지 컬렉션(GC)의 도달 가능성 분석: 일부 GC 알고리즘은 루트(root) 객체에서 시작해 참조 그래프를 레벨 단위로 순회하며 살아있는 객체를 표시한다.

7. 주의할 점

가중치 그래프에는 그대로 쓸 수 없다: 간선마다 가중치가 다르면 BFS의 최단 경로 보장이 깨진다. 이때는 다익스트라(Dijkstra) 알고리즘을 사용해야 한다.
방문 처리 시점: 큐에서 꺼낼 때가 아니라 넣을 때 방문 처리를 해야 중복 삽입을 막을 수 있다. 이를 놓치면 같은 노드가 여러 번 큐에 들어가 성능이 저하된다.
큐 자료구조 선택: 파이썬에서 리스트의 pop(0)을 큐로 쓰면 O(N)이 걸려 전체 알고리즘이 느려진다. collections.deque를 사용해야 O(1) 연산이 보장된다.
무한 루프 방지: 사이클(cycle)이 있는 그래프에서 방문 배열(visited set) 없이 BFS를 구현하면 같은 노드를 무한히 반복 방문할 수 있다.
메모리 사용량: 그래프가 매우 넓게 퍼져 있는(branching factor가 큰) 경우, 한 레벨에 속한 노드 수가 폭발적으로 늘어나 큐가 커지고 메모리 사용량이 급증할 수 있다.

8. 핵심 정리

BFS는 큐의 선입선출(FIFO) 특성을 이용해 시작 노드로부터 가까운 순서대로 레벨 단위로 그래프를 탐색하는 알고리즘이다. 시간 복잡도는 O(V + E)이며, 가중치 없는 그래프에서 최단 경로를 보장한다는 점이 DFS와 구분되는 핵심 특징이다. 방문 처리를 큐에 넣는 시점에 하고, 큐 구현으로는 O(1) 연산이 보장되는 자료구조를 사용하는 것이 실무 구현의 핵심이다.