깊이 우선 탐색 (Depth-First Search, DFS)
DFS(깊이 우선 탐색)는 그래프나 네트워크 탐색 알고리즘 중 하나로, 한 방향으로 갈 수 있을 만큼 깊이 들어간 다음, 더 이상 진행할 수 없을 때 되돌아와(backtracking) 다른 경로를 탐색하는 방식이다.
주로 두 가지 방법으로 구현할 수 있다.
- 재귀호출(Recursive Call)
- 스택(Stack) 자료구조
- DFS는 그래프, 트리, 미로 탐색, 백트래킹 등에 활용된다.
DFS 탐색 과정
예시 그래프:
1
/ \
2 3
| / \
4 5 6| 단계 | 현재 노드 | 방문 순서 | 동작 |
|---|---|---|---|
| 1 | 1 | [1] | 시작 노드 방문 |
| 2 | 2 | [1, 2] | 1의 이웃 중 2로 이동 |
| 3 | 4 | [1, 2, 4] | 2의 이웃 중 4로 이동 |
| 4 | — | [1, 2, 4] | 4에서 더 이상 진행 불가 → 되돌아감 |
| 5 | 3 | [1, 2, 4, 3] | 1의 다음 이웃 3으로 이동 |
| 6 | 5 | [1, 2, 4, 3, 5] | 3의 첫 이웃 |
| 7 | 6 | [1, 2, 4, 3, 5, 6] | 3의 다음 이웃 |
| 8 | — | [1, 2, 4, 3, 5, 6] | 탐색 완료 |
DFS 로직 코드
DFS에는 재귀와 스택 두 가지 방법으로 구현할 수 있다. 각각의 방법의 수도코드를 통해 코드 동작 방식을 알아보자.
(1) 재귀(Recursive) 버전
algorithm dfsRecursion(G, v):
mark v as visited #v 를 방문표시한다.
for each neighbor w of v in G.adjacent(v): #그래프 G에서 v의 각 이웃(인접한 노드) w에 대해:
if w is not visited #만약 w가 아직 방문되지 않았다면:
dfsRecursion(G, w) #재귀설명
G: 그래프 (인접 리스트 혹은 인접 행렬)v: 시작 정점w:v의 인접 노드- 방문 처리는
visited[]배열이나 집합으로 관리 - 호출 스택을 자동으로 이용해 되돌아감(backtracking) 이 이루어진다.
(2) 스택(Stack) 버전
algorithm dfsStack(G, start):
create an empty stack S # 스택 S 생성
push start onto S # start를 S에 추가
mark start as visited # start를 방문표시
while S is not empty: # 스택 S가 모두 pop() 되기 까지 다음을 반복
v ← S.pop() # 스택 S.pop() 값을 v에 저장
for each neighbor w of v in G.adjacent(v): #그래프 G에서 v의 각 이웃(인접한 노드) w에 대해:
if w is not visited: #만약 w가 아직 방문되지 않았다면
mark w as visited #w를 방문표시
push w onto S #스택에다가 w 값 추가설명
- 명시적 스택을 사용하여 재귀 없이 구현.
- push 시 방문 체크를 하면 중복 삽입 방지.
- 탐색 순서는
마지막에 넣은 정점부터 탐색되는 LIFO 구조.
아래 링크를 통해 문제를 통해 DFS를 이해해보자.
백엔드