깊이 우선 탐색 (depth-first search (DFS))
쉽게 풀면
깊이 우선 탐색은 미로를 탐험할 때 한쪽 길을 끝까지 따라가 보고, 막다른 길이면 갈림길로 돌아와 다른 길을 시도하는 방식이다. 너비 우선 탐색이 가까운 곳부터 넓게 퍼지듯 탐색하는 것과 달리, 깊이 우선 탐색은 한 방향으로 최대한 깊이 파고든다. 그래프에 사이클이 있는지 확인하거나, 위상 정렬, 강한 연결 요소를 찾는 등 다양한 그래프 알고리즘의 기반이 된다.
왜 중요한가
깊이 우선 탐색은 컴퓨터과학 전반에서 그래프와 트리 문제를 푸는 가장 기초적인 도구 중 하나이기 때문에, 알고리즘 설계·컴파일러·네트워크 분석 등 다양한 연구에서 반복적으로 활용됩니다. 위상 정렬, 강한 연결 요소 탐색, 미로나 퍼즐의 상태공간 탐색처럼 더 복잡한 알고리즘의 구성 요소로 쓰이는 경우가 많아, 이를 정확히 이해하는 것이 그래프 이론 관련 논문을 읽는 데 필수적입니다.
논문에서는 이렇게 쓰입니다
그래프의 구조적 성질(사이클, 연결성, 위상 순서 등)을 분석하는 알고리즘의 기반 기법으로 인용된다.
스케줄링이나 빌드 시스템 연구에서는 여러 작업 간의 의존관계를 그래프로 표현한 뒤, 깊이 우선 탐색을 이용해 어떤 작업을 먼저 처리해야 하는지 순서를 정하는 데 활용된다는 뜻입니다.
네트워크 분석 연구에서는 사람들 사이의 관계를 그래프로 나타낸 뒤, 서로 긴밀하게 연결된 하위 집단(커뮤니티)을 찾아내는 데 깊이 우선 탐색 기반 알고리즘이 쓰인다는 뜻입니다.
조금 더 깊게 보면
깊이 우선 탐색의 시간복잡도는 일반적으로 정점과 간선의 수에 비례하는 O(V+E)로 알려져 있으며, 각 정점을 방문한 시각(discovery time)과 탐색을 마친 시각(finish time)을 기록하면 사이클 판별이나 위상 정렬 같은 추가 정보를 얻을 수 있습니다. 재귀 호출은 내부적으로 스택을 사용하는 것과 동일하기 때문에, 명시적 스택을 쓰는 반복적 구현과 재귀적 구현은 원리상 같은 탐색 순서를 따릅니다. 논문에서 깊이 우선 탐색을 응용한 알고리즘을 볼 때는 방문 순서를 어떻게 기록하고 활용했는지를 살펴보면 알고리즘의 핵심 아이디어를 파악하기 쉽습니다.
주의할 점
재귀로 구현할 경우 그래프가 매우 크거나 깊으면 스택 오버플로우가 발생할 수 있어, 이런 경우 명시적 스택을 사용한 반복적 구현이 필요하다.