DFS(depth-first search) 깊이 우선 탐색

 

그래프 문제를 풀다 보면 가장 먼저 접하게 되는 탐색 알고리즘이 깊이 우선 탐색(DFS)이다.
DFS는 그래프의 모든 노드를 빠짐없이 방문하기 위한 완전 탐색 기법 중 하나로, 구현이 비교적 직관적이어서 알고리즘 입문 단계에서 자주 사용된다.

이번 글에서는 DFS의 개념, 특징, 시간 복잡도, 그리고 어떤 문제들에 활용되는지까지 간단히 정리해보려고 한다. ✍️

 

 

---

 

 

깊이 우선 탐색이란?

그래프의 시작 노드에서 출발하여 한 방향으로 끝까지 깊게 탐색한 뒤,

더 이상 갈 곳이 없으면 이전 분기점으로 돌아가 다른 경로를 탐색하는 방식의 알고리즘이다.

 

즉,

• 한 노드를 방문하면
• 그 노드와 연결된 노드 중 하나를 선택해
• 최대 깊이까지 탐색을 먼저 수행하고
• 이후 다른 분기를 차례로 탐색한다.

이러한 동작 방식 때문에 DFS는 “깊게 들어갔다가 되돌아온다 🔁 ”는 흐름을 가진다.

노드 안에 번호는 탐색 순서를 나타낸다.

 

 

---

 

 

DFS의 동작 방식과 구현 특징🔧

DFS는 다음 두 가지 방식으로 구현할 수 있다.

1. 재귀 함수 사용
   DFS는 재귀 호출 구조와 매우 잘 어울린다.
   현재 노드를 방문한 뒤, 인접한 노드에 대해 다시 DFS를 호출하는 방식이다.
   다만, 재귀 호출이 깊어질 경우 스택 오버플로(Stack Overflow) ⚠️ 가 발생할 수 있으므로 입력 크기가 큰 문제에서는 주의가 필요하다.
2. 스택(Stack) 자료구조 사용
   재귀를 사용하지 않고, 명시적으로 스택을 이용해 DFS를 구현할 수도 있다.
   이 방식은 재귀 호출에 대한 부담을 줄일 수 있다는 장점이 있다.

 

방문 체크의 중요성 📌

DFS에서는 이미 방문한 노드를 다시 방문하면 안 된다. 

그래프에는 사이클이 존재할 수 있기 때문에, 방문 여부를 체크하지 않으면 같은 노드를 무한히 반복 방문하는 문제가 발생한다.

따라서 DFS 구현 시에는 반드시 다음과 같은 방문 배열이 필요하다.

• visited[node] = true → 방문 처리
• DFS 종료 후 필요하다면 다시 false로 되돌릴 수도 있음 (백트래킹)

 

시간 복잡도⏰

노드의 개수를 V, 에지(간선)의 개수를 E라고 할 때 DFS의 시간 복잡도는 다음과 같다.

O(V + E)

• 모든 노드를 한 번씩 방문하고
• 모든 간선을 한 번씩 확인하기 때문이다.

그래프의 크기가 커져도 효율적으로 동작하는 이유 중 하나다.

 

 

---

 

 

DFS로 풀 수 있는 대표적인 문제들

• 사이클 탐색
  • 그래프에 사이클이 존재하는지 확인할 때 DFS가 사용된다.
  위상 정렬
  • 방향 그래프에서 작업 순서를 정해야 할 때 DFS 기반 위상 정렬을 활용한다.
  단절점(Articulation Point)
  • 특정 노드를 제거했을 때
  • 그래프가 두 개 이상의 컴포넌트로 분리된다면, 그 노드를 단절점이라고 한다.
  단절선(Bridge)
  • 특정 간선을 제거했을 때
  • 그래프가 분리된다면, 그 간선을 단절선이라고 한다.

 

+ 아래 문제들을 풀어 보시면 좋습니다!
https://www.acmicpc.net/workbook/view/1833