깊이 우선 탐색 (DFS)

미로에 들어가 막다른 길이 나올 때까지 가다가, 마지막 갈림길로 되돌아가 다음 길을 시도합니다. 깊이 우선 탐색도 이렇게 그래프를 탐색합니다. 가장 단순한 그래프 알고리즘 중 하나이지만, 이 알고리즘이 쓰는 스택은 생각보다 많은 것을 알려 줍니다.

시작 노드에서 이어진 긴 노드 사슬이 노란색으로 강조되고, 완료된 노드는 연보라색, 스택은 아래에 네모 칸의 줄로 그려진 그래프
시작 노드에서 이어진 긴 노드 사슬이 노란색으로 강조되고, 완료된 노드는 연보라색, 스택은 아래에 네모 칸의 줄로 그려진 그래프

기본 아이디어

그래프는 간선으로 이어진 노드의 집합입니다. 방과 문, 웹 페이지와 링크, 작업과 그 작업이 의존하는 작업처럼요. 깊이 우선 탐색은 시작 노드에서 도달할 수 있는 모든 노드를 방문하지만, 특정한 순서로 방문합니다. 항상 가장 최근에 도달한 노드에서 이어 가는 것이죠. 지금 들어와 있는 노드들을 스택에 보관합니다. 새 노드는 맨 위에 올라가고, 노드는 주변을 모두 탐색한 뒤에만 빠집니다.

단계별 과정

시작 노드를 스택에 넣고 방문 번호 1을 줍니다. 맨 위 노드의 다음 이웃을 봅니다. 아직 보지 않은 노드라면 다음 방문 번호를 주고, 어느 노드에서 도달했는지 기억한 뒤 스택 맨 위에 올립니다. 이미 본 노드라면 건너뜁니다. 맨 위 노드에 확인할 이웃이 남지 않으면 그 노드는 완료입니다. 스택에서 빼고 아래 노드로 이어 갑니다. 스택이 비거나 목표에 도달하면 멈춥니다.

예시

간선 A–B, A–C, B–D, C–D, C–E, D–F가 있는 그래프에서 A부터 시작해, 이웃을 알파벳 순서로 확인합니다. 탐색은 A에서 B로, B에서 D로, D에서 C로, C에서 E로 가므로 스택은 A, B, D, C, E입니다. 그 과정에서 C는 아직 스택에 있는 A를 봅니다. 간선 C–A가 사이클 A, B, D, C를 닫습니다. E에는 새 이웃이 없으므로 완료되고, 이어서 C도 완료되며, 탐색은 아직 F가 남은 D로 되돌아갑니다. 방문 순서는 A, B, D, C, E, F입니다. E를 목표로 하면 DFS는 경로 A → B → D → C → E에서 멈춥니다. 간선이 4개인데, A → C → E는 2개면 됩니다.

어디에 쓰이나

스택은 항상 시작 노드에서 현재 노드까지의 경로이므로, DFS는 미로와 퍼즐에 자연스럽게 맞습니다. 이것이 백트래킹의 아이디어입니다. 방향이 없는 그래프에서 아직 스택에 있는 노드로 가는 간선은 사이클을 닫습니다. 방향이 있는 그래프에서는 노드를 완료된 순서의 역순으로 나열하면 위상 순서가 되어, 각 작업이 그 작업이 의존하는 작업 뒤에 옵니다. 깊이 우선 탐색은 연결 요소, 브리지, 단절점도 찾으며, 무작위 버전은 미로를 만드는 고전적인 방법입니다.

역사

19세기에 프랑스 수학자 샤를 피에르 트레모(Charles Pierre Trémaux)는 통로에 표시를 해서 어떤 미로든 빠져나오는 방법을 설명했는데, 이는 분필로 하는 깊이 우선 탐색입니다. 1972년과 1973년에 로버트 타잔(Robert Tarjan)과 존 홉크로프트(John Hopcroft)는 강한 연결 요소부터 그래프를 교차 없이 그릴 수 있는지 판정하는 문제까지, 많은 그래프 문제를 DFS로 선형 시간에 풀 수 있음을 보였습니다. 두 사람은 이 업적 등으로 1986년 튜링상을 받았습니다.

로버트 타잔. 1972–73년 존 홉크로프트와 함께 깊이 우선 탐색이 많은 그래프 문제를 선형 시간에 푼다는 것을 보였고, 그 공로 등으로 1986년 튜링상을 받았다.
로버트 타잔. 1972–73년 존 홉크로프트와 함께 깊이 우선 탐색이 많은 그래프 문제를 선형 시간에 푼다는 것을 보였고, 그 공로 등으로 1986년 튜링상을 받았다.

직접 해 보기

앱을 열고 단계를 누르세요. 이웃을 확인하는 중인 노드가 강조되고, 스택에 있는 노드는 파란색, 완료된 노드는 초록색이며, 각각 방문 번호가 표시됩니다. 스택은 그래프 아래에 시작 노드부터 맨 위 노드까지 표시됩니다. 상태 표시줄에서 사이클을 닫는 간선을 지켜보고, 목표를 골라 찾은 경로가 너비 우선 탐색과 비교해 얼마나 길어질 수 있는지 확인해 보세요.

자주 묻는 질문

DFS의 시간 복잡도는 얼마인가요?

노드(정점) V개와 간선 E개에 대해 O(V + E)입니다. 각 노드는 스택에 한 번 들어가고 한 번 나오며, 각 간선은 양 끝에서 확인됩니다. 스택과 표시를 위해 O(V)의 추가 메모리가 필요합니다.

DFS는 왜 스택을 사용하나요?

후입선출 덕분에 탐색이 가장 새로운 노드에서 이어 가고, 그 직전 노드로 되돌아갈 수 있기 때문입니다. 재귀는 프로그램의 호출 스택으로 같은 일을 합니다. 대신 큐를 쓰면 탐색은 고리 모양으로 퍼져 나갑니다. 그것이 너비 우선 탐색입니다.

재귀 DFS는 큰 그래프에서 문제가 되나요?

그럴 수 있습니다. 경로가 길면 재귀가 깊어지고, 많은 언어는 호출 깊이를 제한합니다. 반복문에서 명시적 스택을 쓰면 같은 순서로 노드를 방문하면서 이 제한을 피할 수 있습니다.

DFS는 어디에 쓰이나요?

백트래킹으로 미로와 퍼즐 풀기, 사이클 찾기, 의존 관계에 따라 작업 순서 정하기(위상 정렬), 연결 요소와 강한 연결 요소 찾기, 미로 생성, 그리고 의존성 그래프를 따라가는 컴파일러와 빌드 도구에 쓰입니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

깊이 우선 탐색 해 보기