DFS(Depth First Search)

DFS(Depth First Search)는 그래프를 탐색하는 대표적인 방법 중 하나로, 이름 그대로 한 방향으로 가능한 한 깊이까지 들어가며 탐색하는 방식이다. 그래프에서 노드들이 어떻게 연결되어 있는지를 따라가며 구조를 파악해야 할 때 자주 사용된다. 이전에 다뤘던 그래프가 “연결 관계를 표현하는 자료구조”였다면, DFS는 그 연결 관계를 어떤 순서로 방문할 것인가에 대한 방법이라고 볼 수 있다.

DFS의 가장 큰 특징은 탐색 순서에 있다. 현재 위치에서 갈 수 있는 노드가 있다면, 다른 선택지를 남겨두더라도 일단 그 방향으로 계속 이동한다. 그러다 더 이상 갈 수 없는 지점에 도달하면, 그제서야 이전 노드로 되돌아와 다른 경로를 탐색한다. 이 흐름은 마치 미로에서 한 갈래 길을 끝까지 따라갔다가 막히면 되돌아오는 방식과 매우 유사하다. 그래서 DFS는 “깊게 들어갔다가 돌아온다”는 이미지로 이해하면 가장 직관적이다.

이러한 탐색 방식 때문에 DFS는 구조적으로 되돌아오는 과정이 필수적이다. 이 되돌아오는 흐름은 보통 스택 구조로 표현되며, 실제 구현에서도 스택이나 재귀 호출을 통해 자연스럽게 구현된다. 중요한 점은 이미 방문한 노드를 다시 방문하지 않도록 관리해야 한다는 것이다. 그래프는 트리와 달리 사이클이 존재할 수 있기 때문에, 방문 여부를 체크하지 않으면 같은 노드를 무한히 반복해서 탐색하는 문제가 발생할 수 있다. 따라서 DFS에서는 “방문 처리”가 알고리즘의 핵심 요소 중 하나다.

DFS의 시간 복잡도는 그래프의 표현 방식과 밀접한 관련이 있다. 인접 리스트로 그래프를 표현한 경우, DFS는 각 노드를 한 번씩 방문하고, 각 간선을 한 번씩 확인한다. 이 때문에 시간 복잡도는 O(N + M)으로 정리된다. 여기서 N은 노드의 개수, M은 간선의 개수다. 즉, 그래프의 크기가 커질수록 탐색 시간도 그에 비례해 증가하지만, 불필요한 중복 탐색 없이 전체 구조를 한 번 훑는 수준이라고 볼 수 있다. 이 점에서 DFS는 효율적인 그래프 탐색 방법 중 하나다.

DFS는 특히 “모든 경우를 끝까지 확인해야 하는 문제”에 강점을 가진다. 예를 들어 경로가 존재하는지 확인하는 문제, 특정 조건을 만족하는 경로를 찾는 문제, 사이클이 존재하는지 판별하는 문제, 혹은 선택지를 하나씩 깊게 파고들며 답을 찾는 백트래킹 문제에서 DFS는 거의 기본 도구처럼 사용된다. 한 번 선택한 경로를 끝까지 탐색한 뒤에 다음 선택지로 넘어간다는 특성이 이러한 문제들과 잘 맞아떨어지기 때문이다.

정리해보면, DFS는 그래프 탐색의 기본이 되는 알고리즘으로, “깊이 우선”이라는 명확한 탐색 철학을 가지고 있다. 한 방향으로 최대한 깊이 들어갔다가 되돌아오는 흐름, 방문 여부를 통한 중복 방지, 그리고 O(N + M)이라는 직관적인 시간 복잡도만 이해하고 있어도 DFS의 전체 구조는 충분히 이해할 수 있다. 이 개념을 확실히 잡아두면 이후에 배우게 될 BFS나 다양한 그래프 응용 문제들도 훨씬 수월하게 받아들일 수 있다.