너비 우선 탐색

너비 우선 탐색은 그래프에서 출발점과 가까운 곳부터 차례로 훑는 방법입니다. 바로 이웃한 곳을 모두 본 뒤에야 이웃의 이웃으로 넘어갑니다. 그래서 훑기가 끝나면 각 곳이 출발점에서 몇 번 건너야 닿는지도 함께 알게 됩니다.

상세

연못에 돌을 던지면 돌이 떨어진 곳에서 물결이 둥글게 퍼집니다. 가까운 물이 먼저 흔들립니다. 한 바퀴 바깥의 물은 그다음에 흔들립니다. 먼 물이 가까운 물보다 먼저 흔들리는 일은 없습니다.

너비 우선 탐색은 그래프 위에서 이 물결을 흉내 냅니다. 영어 이름은 Breadth-First Search 입니다. 줄여서 BFS 라고 부릅니다. 「너비 우선」은 한 갈래를 깊이 파고들기 전에 옆으로 넓게 먼저 훑는다는 뜻입니다.

그래프와 거리

그래프는 대상들과 그 사이의 연결을 담는 구조입니다. 누가 누구와 연결돼 있는지를 적어 둘 때 씁니다. 메신저의 친구 관계가 그런 예입니다.

그래프에서 대상 하나를 노드라고 부릅니다. 두 노드를 잇는 선 하나는 간선이라고 부릅니다. 메신저라면 사람이 노드입니다. 친구 관계는 간선입니다.

이 편에서 거리는 출발점에서 간선을 몇 번 건너야 닿는지를 센 수입니다. 내 친구는 거리 1 입니다. 친구의 친구는 거리 2 입니다. 간선마다 길이나 요금 같은 값이 붙어 있어도 너비 우선 탐색은 그 값을 보지 않고 건넌 횟수만 셉니다.

넣는 것과 나오는 것

넣는 것은 그래프 하나와 출발 노드 하나입니다. 나오는 것은 출발점에서 닿는 노드 전부와 각 노드의 거리입니다. 어느 간선으로도 닿지 않는 노드는 결과에 나오지 않습니다.

노드마다 「어느 노드를 거쳐 처음 닿았나」도 함께 적어 둘 수 있습니다. 이 기록을 끝에서부터 거꾸로 따라가면 출발점까지 가장 짧은 길이 나옵니다. 박 과장과 나 사이에 누가 끼어 있는지가 이 길입니다.

큐로 순서를 지키는 절차

큐는 먼저 넣은 것이 먼저 나오는 줄입니다. 뒤로 넣고 앞에서 꺼냅니다. 너비 우선 탐색은 가까운 노드부터 훑는 순서를 이 큐 하나로 지킵니다.

방문 표시도 하나 둡니다. 큐에 한 번 넣은 노드에 붙여 두는 표시입니다. 같은 노드를 큐에 두 번 넣지 않으려고 둡니다.

그래프에는 몇 번 건너다 보면 제자리로 돌아오는 길이 있을 수 있습니다. 이런 길을 사이클이라고 합니다. 표시가 없으면 사이클을 따라 같은 노드를 끝없이 다시 넣습니다.

절차는 네 단계입니다.

1. 출발 노드에 거리 0 을 적습니다. 표시를 한 뒤 큐에 넣습니다.
2. 큐 맨 앞에서 노드 하나를 꺼냅니다.
3. 꺼낸 노드의 이웃을 하나씩 봅니다. 표시가 없는 이웃에는 「꺼낸 노드의 거리 + 1」을 적습니다. 그 이웃에 표시를 한 뒤 큐 뒤에 넣습니다.
4. 큐가 빌 때까지 2 와 3 을 되풀이합니다.

표시는 큐에 넣을 때 합니다. 꺼낼 때 하면 같은 노드가 큐에 두 번 들어갈 수 있습니다. 아래 예의 D 가 그럴 뻔한 노드입니다.

여섯 노드로 따라가 보기

아래 그래프는 노드 여섯과 간선 일곱으로 이루어져 있습니다. 간선에 방향이 없어서 어느 쪽으로든 건널 수 있습니다. A 에서 출발합니다. 그림은 훑기가 끝난 뒤 알게 되는 거리에 따라 노드를 묶어 놓았습니다.

flowchart TD
    subgraph G0["거리 0"]
        A
    end
    subgraph G1["거리 1"]
        B
        C
    end
    subgraph G2["거리 2"]
        D
        E
    end
    subgraph G3["거리 3"]
        F
    end
    A --- B
    A --- C
    B --- D
    C --- D
    C --- E
    D --- F
    E --- F

아래 표는 큐에서 노드를 하나씩 꺼낼 때마다 무엇이 바뀌는지 적은 것입니다.

꺼낸 순서를 위에서부터 읽으면 거리가 0, 1, 1, 2, 2, 3 입니다. 먼 노드가 가까운 노드보다 먼저 나온 적이 한 번도 없습니다. 그림의 묶음을 위에서 아래로 읽은 순서와 같습니다.

C 를 꺼낼 때 D 에는 B 가 이미 표시를 해 두었습니다. 그래서 D 는 큐에 한 번만 들어갑니다. 표시를 꺼낼 때 했다면 B 와 C 가 D 를 한 번씩 넣었을 겁니다.

어디서 왔나도 적었다면 F 는 D 에서, D 는 B 에서, B 는 A 에서 왔습니다. 이를 거꾸로 읽은 A → B → D → F 가 A 에서 F 까지 가장 짧은 길입니다. A → C → E → F 도 간선 셋이라 똑같이 짧습니다. 너비 우선 탐색은 그중 먼저 찾은 하나를 내놓습니다.

가장 짧은 길이 나오는 까닭

닿는 노드를 모으기만 할 거라면 방문 순서는 상관없습니다. 순서를 아무렇게나 두면 처음 닿았을 때 센 횟수가 먼 길로 돌아온 횟수일 수 있습니다. 너비 우선 탐색이 가까운 순서를 굳이 지키는 까닭은 처음 센 횟수를 곧바로 가장 짧은 거리로 쓰기 위해서입니다.

큐 안에는 늘 거리가 많아야 두 가지뿐입니다. 거리 d 인 노드들이 앞에 섭니다. 거리 d + 1 인 노드들은 뒤에 섭니다. 거리 d 인 노드를 꺼내면 그 이웃은 d + 1 을 받아 맨 뒤에 붙기 때문입니다.

그래서 노드는 거리가 짧은 순서로 큐에서 나옵니다. 어떤 노드에 처음 닿는 때는 그 노드의 이웃 가운데 출발점에서 거리가 가장 짧은 이웃을 꺼냈을 때입니다. 그 이웃의 거리에 1 을 더한 값이 이 노드의 거리로 적힙니다.

이보다 짧은 길이 있었다고 해 보겠습니다. 그 길에서 이 노드 바로 앞의 이웃은 거리가 더 작으니 큐에서 더 먼저 나왔을 겁니다. 그러면 이 노드에도 그때 먼저 닿았어야 합니다. 처음 닿은 때와 어긋나므로 처음 적힌 거리보다 짧은 길은 있을 수 없습니다.

코드로 옮긴 모양

아래는 파이썬으로 옮긴 것입니다. 그래프는 노드마다 이웃 목록을 적은 딕셔너리로 담았습니다. 이렇게 노드마다 이웃 목록을 두는 방식을 인접 리스트라고 합니다.

from collections import deque

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

def bfs(graph, start):
    dist = {start: 0}
    parent = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                parent[nxt] = node
                queue.append(nxt)
    return dist, parent

deque 는 파이썬이 주는 큐입니다. append 로 뒤에 넣고 popleft 로 앞에서 꺼냅니다.

dist 는 노드마다 거리를 적은 표입니다. 여기에 이름이 있으면 표시가 된 노드로 칩니다. 거리 기록이 방문 표시를 겸하는 셈입니다.

parent 는 노드마다 어디서 왔나를 적은 표입니다. 앞의 예로 돌리면 아래 값이 나옵니다.

dist, parent = bfs(graph, "A")
dist["F"]      # 3
parent["F"]    # 'D'
parent["D"]    # 'B'

parent 를 F 에서 시작해 거꾸로 따라가면 D, B, A 가 나옵니다. 앞 절에서 표로 따라간 길과 같습니다.

드는 비용

비용은 노드 수와 간선 수로 적습니다. 노드 수를 V, 간선 수를 E 라고 쓰겠습니다. V 는 vertex(꼭짓점), E 는 edge(간선)의 첫 글자입니다.

모든 노드는 큐에 한 번 들어가고 한 번 나옵니다. 꺼낸 노드마다 이웃 목록을 한 번 봅니다. 방향 없는 간선은 양 끝 노드에서 한 번씩, 모두 두 번 보게 됩니다. 그래서 일의 양은 노드 수와 간선 수를 더한 만큼에 비례합니다.

입력이 커질 때 비용이 늘어나는 모양을 적는 약속을 빅오 표기법이라고 합니다. 이 표기로 인접 리스트 위의 너비 우선 탐색은 시간이 O(V + E) 입니다.

그래프를 노드 × 노드 크기의 칸표로 담으면 사정이 다릅니다. 이 방식을 인접 행렬이라고 합니다. 한 노드의 이웃을 찾으려면 그 노드의 줄 V 칸을 다 봐야 합니다. 노드마다 그러니 시간이 O(V²) 이 됩니다.

간선이 노드 수에 견줘 드물면 인접 리스트가 인접 행렬보다 훨씬 적게 봅니다. 간선이 V 개 남짓이면 한쪽은 V 에 비례하고 다른 쪽은 V² 에 비례합니다.

큐가 불어나는 모양

메모리에서 눈여겨볼 것은 큐입니다. 큐에는 같은 거리의 노드가 한꺼번에 몰립니다. 가지가 넓게 퍼지는 그래프일수록 이 무리가 커집니다.

노드마다 새 이웃이 열 개씩 붙는 트리를 생각해 보겠습니다. 트리는 사이클 없이 가지만 뻗어 나가는 그래프입니다. 이 트리를 뿌리에서부터 탐색하면 거리가 하나 늘 때마다 노드가 열 배가 됩니다.

거리 1 에는 노드가 10 개, 거리 2 에는 100 개 있습니다. 거리 6 에 이르면 100 만 개가 됩니다. 거리 6 에 닿을 즈음 큐에는 이 100 만 개가 거의 다 들어 있습니다. 찾던 노드가 거리 6 에 있으면 그 앞의 모든 거리를 다 쌓았다가 비운 뒤입니다.

깊이 우선 탐색과 가르는 기준

그래프를 훑는 또 하나의 기본 방법이 깊이 우선 탐색입니다. 한 갈래를 끝까지 파고듭니다. 막히면 되돌아 나와 다른 갈래로 갑니다. 줄여서 DFS(Depth-First Search)라고 부릅니다.

깊이 우선 탐색은 큐 대신 스택을 씁니다. 스택은 나중에 넣은 것이 먼저 나오는 더미입니다. 방금 찾은 이웃부터 파고들게 되므로 순서가 깊이 쪽으로 기웁니다.

앞의 열 갈래 트리를 깊이 우선으로 탐색하면 거리 6 까지 내려가도 붙들고 있는 노드가 수십 개입니다. 지나온 한 갈래와 그 옆 형제들만 들고 있기 때문입니다.

간선 수로 가장 짧은 길이 필요하면 너비 우선 탐색을 씁니다. 닿는지만 알면 되는 문제에서 그래프가 넓게 퍼져 있으면 깊이 우선 탐색이 메모리를 덜 씁니다.

간선에 가중치가 붙은 그래프

간선마다 길이나 요금 같은 값이 붙은 그래프를 가중 그래프라고 합니다. 간선에 붙은 값은 가중치라고 부릅니다. 너비 우선 탐색은 가중치를 보지 않고 건넌 횟수만 셉니다. 그래서 간선 수가 가장 적은 길이 가장 싼 길과 다를 수 있습니다.

X 에서 Z 로 바로 가는 간선의 가중치가 10 이라고 하겠습니다. Y 를 거쳐 가는 두 간선은 가중치가 1 씩입니다. 너비 우선 탐색은 간선 하나짜리인 10 짜리 길을 먼저 찾습니다. 가중치를 더하면 2 인 길이 있는데도 그렇습니다.

가중치의 합이 가장 작은 길은 다익스트라 알고리즘이 구합니다. 가중치에 음수가 없을 때 쓰는 절차입니다. 모든 간선의 가중치가 같으면 건넌 횟수만으로 가중치의 합을 비교할 수 있습니다. 그래서 너비 우선 탐색으로 충분합니다.

너비 우선 탐색이 밑에 깔린 문제

「몇 번 만에 닿나」나 「가까운 순서로」를 묻는 문제면 대개 이 절차가 밑에 깔립니다. 노드와 간선이 무엇인지만 정하면 같은 코드가 돕니다.

셋째 줄처럼 링크를 따라 웹 페이지를 모으는 프로그램을 웹 크롤러라고 합니다. 가까운 페이지부터 모으면 「링크 세 번 안쪽까지만」처럼 거리로 끊어 멈추기 쉽습니다.

넷째 줄의 덩어리를 연결 요소라고 부릅니다. 아직 표시 안 된 노드에서 새로 탐색을 시작할 때마다 덩어리가 하나씩 늘어납니다.

다섯째 줄은 이분 그래프 판정입니다. 모든 간선이 두 편 사이만 잇도록 노드를 가를 수 있는 그래프가 이분 그래프입니다. 거리의 홀짝으로 편을 가른 뒤 같은 편끼리 잇는 간선이 하나라도 있으면 이분 그래프가 아닙니다.

위상 정렬 안의 너비 우선 탐색

간선에 방향이 있고 사이클이 없는 그래프를 DAG(Directed Acyclic Graph, 방향 비순환 그래프)라고 합니다. 방향이 있는 간선을 이 절에서는 화살표라고 부르겠습니다. 빌드할 파일들의 의존 관계가 이런 그래프입니다. main.c 에서 main.o 로, main.o 에서 실행 파일로 화살표가 갑니다.

DAG 의 노드를 화살표를 거스르지 않게 한 줄로 세우는 일을 위상 정렬이라고 합니다. 앞의 빌드라면 main.c, main.o, 실행 파일 순서가 답입니다. 이 순서대로 만들면 쓸 파일이 늘 먼저 준비돼 있습니다.

위상 정렬을 큐로 푸는 방법은 너비 우선 탐색과 모양이 같습니다. 들어오는 화살표가 없는 노드부터 큐에 넣습니다. 하나를 꺼낼 때마다 그 노드에서 나가는 화살표를 지웁니다. 그러다 들어오는 화살표가 하나도 안 남은 노드가 생기면 큐 뒤에 넣습니다.

거리 대신 「앞선 것이 다 끝났나」를 보고 큐에 넣는다는 점만 다릅니다. 큐에서 나온 순서가 그대로 위상 정렬의 답이 됩니다.

관련 항목

너비 우선 탐색이 속하는 상위 분류

알고리즘 · 그래프 알고리즘 · 그래프 탐색 · 탐색 알고리즘

너비 우선 탐색이 훑는 그래프의 구성 요소

그래프 · 노드 · 간선 · 사이클 · 방향 그래프 · 무방향 그래프 · 가중 그래프 · 트리 · DAG

너비 우선 탐색을 이루는 부품

큐 · 덱 · 방문 표시 · 인접 리스트 · 인접 행렬 · 해시테이블 · 집합

같은 그래프를 다른 순서로 훑는 방법

깊이 우선 탐색 · 스택 · 재귀 · 반복 심화 깊이 우선 탐색 · 백트래킹

너비 우선 탐색을 고쳐 쓴 변형

양방향 탐색 · 0-1 BFS · 다중 출발점 너비 우선 탐색 · 레벨 순서 순회

가중치가 붙은 그래프에서 대신 쓰는 최단 경로 알고리즘

최단 경로 · 다익스트라 알고리즘 · 벨만-포드 알고리즘 · 플로이드 알고리즘

너비 우선 탐색 위에 얹힌 알고리즘

위상 정렬 · 칸 알고리즘 · 연결 요소 · 이분 그래프 · 에드몬즈-카프 알고리즘 · 웹 크롤러

너비 우선 탐색의 비용을 적는 표기

빅오 표기법 · 시간 복잡도 · 공간 복잡도