깊이 우선 탐색

깊이 우선 탐색은 그래프에서 한 점을 출발해 닿을 수 있는 점을 빠짐없이 찾아가는 방법입니다. 한 갈래를 막힐 때까지 끝까지 들어간 뒤 되돌아 나와 다음 갈래로 갑니다. 두 점이 이어져 있는지, 관계가 빙 돌아 처음으로 되돌아오는지를 알아낼 때 씁니다.

상세

그래프는 무엇과 무엇이 이어져 있는지를 점과 선으로 담는 자료구조입니다. 점 하나를 노드라고 부릅니다. 두 노드를 잇는 선은 간선이라고 부릅니다. 간선 하나로 바로 이어진 노드끼리는 서로 이웃입니다.

그래프에는 줄이나 계층 같은 정해진 순서가 없습니다. 어디부터 어디로 훑을지를 쓰는 쪽이 정해야 합니다. 규칙 없이 간선을 따라가면 어떤 노드는 빠뜨립니다. 어떤 노드는 여러 번 봅니다. 깊이 우선 탐색은 그 규칙 가운데 하나입니다.

동굴 탐사가 이 규칙과 닮았습니다. 갈림길을 만나면 굴 하나를 골라 막다른 곳까지 들어갑니다. 막히면 마지막 갈림길로 돌아와 아직 안 들어간 굴로 갑니다. 들어갔던 굴 입구에는 분필로 표시를 남깁니다.

이 비유에서 갈림길은 노드입니다. 굴은 간선입니다. 분필 표시는 아래에서 볼 방문 표시입니다.

이름의 「깊이」는 출발점에서 얼마나 멀리 들어갔는지를 가리킵니다. 가까운 노드를 넓게 훑기 전에 멀리 들어가는 쪽을 먼저 합니다. 영어 이름은 Depth-First Search 입니다. 줄여서 DFS 라고 씁니다.

넣는 것은 그래프와 출발 노드 하나입니다. 나오는 것은 출발점에서 닿을 수 있는 노드 전부와 그 노드들을 들른 순서입니다. 모듈 사이의 불러 쓰기 관계를 그래프로 적어 둔 것이 의존성 그래프입니다. 한 모듈에서 출발해 닿는 노드를 모으면 그 모듈이 결국 기대는 모듈 목록이 나옵니다.

한 갈래씩 끝까지 들어가는 순서

노드 다섯 개짜리 그래프 하나로 순서를 따라갑니다. 간선에 방향이 없어서 양쪽으로 오갈 수 있습니다. A 와 B 가 이어져 있으면 A 에서 B 로도, B 에서 A 로도 갑니다.

flowchart TD
    A["A"] --- B["B"]
    A --- C["C"]
    B --- D["D"]
    C --- D
    D --- E["E"]

이웃이 여럿이면 알파벳 순서로 앞선 이웃부터 들어간다고 정합니다. 어느 이웃부터 가도 깊이 우선 탐색입니다. 들르는 순서만 달라집니다. 아래 표는 A 에서 출발한 탐색을 한 줄씩 적은 것입니다.

들른 순서는 A · B · D · C · E 입니다. C 는 A 바로 옆의 노드입니다. 그런데도 네 번째에야 들렀습니다. B 쪽 갈래를 D 까지 먼저 파고들었기 때문입니다.

한 노드에서 하는 일은 늘 같습니다. 표의 일곱 줄을 한 노드의 일로 줄이면 아래 갈림이 됩니다.

flowchart TD
    S["노드에 들어온다"] --> M["다녀갔다고 표시한다"]
    M --> Q{"안 간 이웃이 남았나"}
    Q -->|"남았다"| G["그 이웃으로 들어간다"]
    G --> S
    Q -->|"없다"| R{"출발 노드인가"}
    R -->|"아니다"| K["들어오기 전의 노드로 돌아간다"]
    K --> Q
    R -->|"그렇다"| F["끝난다"]

돌아간 노드에서는 다시 「안 간 이웃이 남았나」부터 묻습니다. 표의 5번 줄에서 D 로 돌아와 E 를 찾은 것이 이 물음입니다.

다녀간 노드 표시

표에서 「이미 갔다」를 여러 번 확인했습니다. 이 확인이 없으면 탐색이 끝나지 않습니다.

위 그래프에는 A → B → D → C → A 로 한 바퀴 도는 길이 있습니다. 출발한 노드로 되돌아오는 이런 고리를 사이클이라고 합니다. 표시 없이 이웃을 따라가기만 하면 이 사이클을 끝없이 돕니다.

그래서 들른 노드를 따로 적어 둡니다. 이 기록을 방문 표시라고 부릅니다. 동굴 입구에 남긴 분필 표시가 이것입니다. 방문 표시는 흔히 집합에 담습니다.

집합은 같은 값을 두 번 담지 않는 모음입니다. 해시테이블로 만든 집합은 노드가 많아도 들렀는지를 거의 일정한 시간에 답합니다.

부모에서 자식으로만 내려가는 트리에서는 표시 없이도 탐색이 끝납니다. 같은 노드로 돌아오는 길이 없기 때문입니다.

지나온 길을 쌓아 두는 스택

되돌아가려면 어디서 왔는지 알아야 합니다. 표의 셋째 칸 「지나온 길」이 그 기록입니다.

이 길은 한쪽 끝에서만 늘고 줄어듭니다. 들어갈 때 끝에 하나를 붙입니다. 막혀서 돌아갈 때 끝에서 하나를 뗍니다. 마지막에 넣은 것을 먼저 꺼내는 이런 자료구조를 스택이라고 합니다.

코드로 쓸 때는 재귀를 자주 씁니다. 재귀는 함수가 자기 자신을 다시 부르는 것입니다. 안 간 이웃을 만날 때마다 같은 함수를 한 번 더 부르면 한 갈래를 끝까지 들어갑니다.

함수를 부르면 언어가 돌아올 곳을 호출 스택에 쌓아 둡니다. 안쪽 함수가 끝나면 거기서 하나를 꺼내 바깥 함수로 돌아옵니다. 그래서 스택을 따로 만들지 않아도 지나온 길이 기억됩니다.

아래 코드는 앞의 그래프를 파이썬으로 옮긴 것입니다. graph 는 노드마다 이웃 목록을 붙여 둔 딕셔너리입니다. 이렇게 이웃 목록으로 그래프를 담는 방식을 인접 리스트라고 합니다. seen 은 방문 표시를 담습니다. order 는 들른 순서를 담습니다.

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}
seen = set()
order = []

def dfs(node):
    seen.add(node)
    order.append(node)
    for nxt in graph[node]:
        if nxt not in seen:
            dfs(nxt)

dfs("A")
print(order)  # ['A','B','D','C','E']

dfs 는 안 간 이웃을 만날 때마다 자기 자신을 한 번 더 부릅니다. 안쪽 호출이 끝나면 바깥 호출의 for 로 돌아옵니다. 이 돌아옴이 표의 「막혀서 돌아간다」입니다.

호출 스택에는 크기 한도가 있습니다. 갈래가 아주 길면 호출이 그 한도를 넘어 스택 오버플로가 납니다. 그럴 때는 리스트로 스택을 직접 만듭니다.

반복문은 스택에서 노드를 하나 꺼냅니다. 그 노드의 안 간 이웃을 스택에 넣습니다. 스택이 빌 때까지 이 둘을 되풀이합니다.

이렇게 쓰면 들르는 순서가 재귀 코드와 달라질 수 있습니다. 스택은 마지막에 넣은 것을 먼저 꺼냅니다. 그래서 A 의 이웃을 B, C 순서로 넣으면 C 부터 들릅니다. 이웃을 거꾸로 넣으면 재귀 코드와 순서를 맞출 수 있습니다.

드는 시간과 메모리

노드 수를 n, 간선 수를 m 이라고 하겠습니다. 탐색은 노드마다 한 번 들어가 표시합니다. 들어간 노드에서는 그 노드의 이웃 목록을 한 번 훑습니다.

이웃 목록을 모두 합치면 간선 하나가 두 번 나옵니다. 방향 없는 간선은 양 끝 노드의 목록에 한 번씩 적히기 때문입니다. 그래서 전체 일의 양은 노드 수에 간선 수의 두 배를 더한 만큼입니다.

이것을 빅오 표기법으로 O(n + m) 이라고 적습니다. 빅오 표기법은 입력이 커질 때 비용이 어떤 모양으로 따라 늘어나는지를 적는 약속입니다. 모양만 보므로 두 배 같은 고정된 곱은 떼고 적습니다.

그래프를 인접 행렬로 담으면 사정이 다릅니다. 인접 행렬은 노드 수만큼 줄과 칸을 둔 표에 두 노드가 이어졌는지를 적는 방식입니다. 이웃을 찾으려면 한 줄을 끝까지 봐야 하므로 전체가 O(n²) 이 됩니다.

메모리는 그래프를 담는 공간을 빼고 셉니다. 탐색이 따로 쓰는 것은 방문 표시와 지나온 길입니다. 둘 다 노드 수를 넘지 않습니다.

노드가 한 줄로 길게 이어진 그래프라면 지나온 길이 노드 수만큼 길어집니다. 아래 표는 담는 방식에 따라 두 비용을 견준 것입니다.

너비 우선 탐색과 갈리는 점

같은 질문을 다른 순서로 푸는 짝이 너비 우선 탐색입니다. 출발점에서 가까운 노드부터 한 겹씩 넓혀 가며 들릅니다.

너비 우선 탐색은 다음에 들를 노드를 큐에 담습니다. 큐는 먼저 넣은 것을 먼저 꺼내는 자료구조입니다. 스택과 꺼내는 쪽이 반대라서 들르는 순서가 갈립니다.

앞의 다섯 노드 그래프에 두 방법을 돌리면 아래처럼 갈립니다.

A 와 C 는 간선 하나로 바로 이어져 있습니다. 그런데 깊이 우선 탐색은 C 에 A → B → D → C 로 간선 세 개를 거쳐 닿았습니다. 가장 짧은 길이 필요하면 너비 우선 탐색을 씁니다. 간선마다 길이가 다르면 다익스트라 알고리즘 같은 최단 경로 알고리즘이 맡습니다.

깊이 우선 탐색으로 푸는 질문

한 갈래를 끝까지 판 뒤에 돌아 나온다는 성질 덕에 쉽게 풀리는 질문이 몇 있습니다.

두 노드 사이에 길이 있는지는 한쪽에서 탐색을 돌려 보면 압니다. 다른 쪽에 표시가 붙었으면 길이 있습니다. 표시가 안 붙은 노드에서 탐색을 다시 시작하기를 되풀이하면 그래프가 몇 덩어리로 나뉘는지도 셉니다. 서로 이어진 이 한 덩어리를 연결 요소라고 합니다.

방향 그래프는 간선에 화살표가 있어 한쪽으로만 가는 그래프입니다. 모듈 A 가 B 를 불러 쓰면 A 에서 B 로 화살표를 긋는 식입니다. 이런 그래프의 사이클은 서로가 서로를 불러 쓰는 순환 의존입니다.

방향 그래프에서 사이클을 찾으려면 표시를 셋으로 나눕니다. 노드마다 아래 세 상태를 차례로 거칩니다. 세 상태를 차례로 흰색 · 회색 · 검은색이라고도 부릅니다.

stateDiagram-v2
    state "안 감" as 안감
    state "탐색 중" as 탐색중
    state "끝남" as 끝남
    [*] --> 안감
    안감 --> 탐색중: 들어간다
    탐색중 --> 끝남: 이웃을 다 보고 나온다

「탐색 중」인 노드는 지금 지나온 길 위에 있는 노드입니다. 탐색하다가 「탐색 중」인 노드로 가는 화살표를 만나면 지나온 길로 되돌아가는 고리가 있습니다. 그것이 사이클입니다.

「끝남」인 노드를 다시 만나는 것은 사이클이 아닙니다. 아래 그래프에서 D 는 B 쪽 갈래에서 먼저 끝납니다.

flowchart TD
    A["A"] --> B["B"]
    A --> C["C"]
    B --> D["D"]
    C --> D

C 쪽 갈래에서 D 를 다시 만날 때 D 는 이미 「끝남」입니다. 화살표를 따라 A 로 돌아오는 길이 없으니 사이클이 아닙니다. 표시가 「갔다」 하나뿐이면 이 만남을 사이클로 잘못 읽습니다.

사이클이 없는 방향 그래프를 DAG(Directed Acyclic Graph, 방향 비순환 그래프)라고 부릅니다. DAG 에서는 화살표를 거스르지 않는 한 줄 순서를 뽑을 수 있습니다. 이 일을 위상 정렬이라고 합니다. Maven 이 여러 모듈 가운데 무엇부터 빌드할지 정하는 일이 이 꼴입니다.

깊이 우선 탐색으로 위상 정렬을 하는 방법은 짧습니다. 노드가 「끝남」이 되는 순서를 적어 두었다가 뒤집습니다. 한 노드는 화살표로 가리키는 노드가 모두 끝난 뒤에야 끝나기 때문입니다.

위 그래프라면 D · B · C · A 순서로 끝납니다. 뒤집으면 A · C · B · D 입니다. 이 순서에서는 화살표를 긋는 쪽, 곧 불러 쓰는 모듈이 앞에 섭니다.

빌드는 불려 쓰이는 모듈부터 해야 합니다. 앞에서처럼 불러 쓰는 쪽에서 화살표를 그었다면 뒤집기 전의 끝남 순서 D · B · C · A 가 곧 빌드 순서입니다.

트리와 선택지 위의 깊이 우선 탐색

트리에서 도는 깊이 우선 탐색은 노드를 언제 결과에 적느냐에 따라 이름이 갈립니다. 적는다는 것은 앞 코드의 order.append 처럼 들른 노드를 결과 목록에 넣는 일입니다.

앞 코드는 노드에 들어오자마자 적습니다. 자식보다 먼저 적는 이 순서를 전위 순회라고 합니다.

자식을 다 본 뒤에 적으면 후위 순회입니다. 방향 그래프에서 노드가 「끝남」이 되는 순서가 이 순서입니다.

자식이 둘인 트리에서는 순서가 하나 더 있습니다. 왼쪽 자식을 다 본 뒤, 오른쪽 자식으로 가기 전에 적으면 중위 순회입니다.

퍼즐이나 조합 문제는 답 후보를 하나씩 골라 가다가 막히면 직전 선택으로 돌아갑니다. 이 방법을 백트래킹이라고 합니다. 선택지들이 이루는 트리를 깊이 우선으로 도는 것과 같습니다.

맞지 않는 경우

가장 짧은 길을 찾아야 하면 맞지 않습니다. 앞의 C 처럼 먼저 닿은 길이 짧다는 보장이 없습니다.

그래프가 끝없이 크거나 아주 깊으면 한 갈래에 빠져 돌아오지 못합니다. 체스처럼 수를 둘 때마다 새 판이 생기는 문제가 그렇습니다. 판 하나가 노드 하나입니다. 수 하나는 간선 하나입니다.

이럴 때는 들어갈 깊이에 한도를 두는 깊이 제한 탐색을 씁니다. 한도보다 깊이 가면 막힌 것으로 치고 돌아 나옵니다.

한도를 1, 2, 3 으로 조금씩 늘려 가며 깊이 제한 탐색을 되풀이하는 방법이 반복 심화 깊이 우선 탐색입니다. 얕은 곳에 있는 답을 먼저 찾습니다. 그러면서도 메모리는 깊이 우선 탐색만큼만 씁니다.

관련 항목

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

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

깊이 우선 탐색이 도는 자료구조

그래프 · 방향 그래프 · 트리 · DAG · 인접 리스트 · 인접 행렬 · 의존성 그래프

깊이 우선 탐색이 지나온 길과 표시를 담는 자료구조

스택 · 재귀 · 호출 스택 · 스택 오버플로 · 집합 · 해시테이블 · 방문 표시

같은 그래프를 다른 순서로 훑는 탐색

너비 우선 탐색 · 깊이 제한 탐색 · 반복 심화 깊이 우선 탐색 · 양방향 탐색 · 최선 우선 탐색

깊이 우선 탐색으로 푸는 그래프 문제

사이클 검출 · 위상 정렬 · 연결 요소 · 강연결 요소 · 이분 그래프 · 단절점 · 도달 가능성 · 순환 의존성

깊이 우선 탐색을 트리와 선택지에 적용한 갈래

전위 순회 · 중위 순회 · 후위 순회 · 백트래킹

가장 짧은 길을 찾는 알고리즘

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

드는 비용을 적는 표기

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