그래프나 트리와 같은 자료 구조에서 한 노드에서 시작해 가능한 한 깊숙이 탐색하는 알고리즘
- 막다른 길에 다다르면 이전 노드로 돌아와(백트래킹) 다른 경로를 탐색하는 방식으로 동작
⭐ DFS의 특징
✅ 1. 깊이 우선 탐색
- 현재 노드에서 방문하지 않은 인접 노드가 있다면, 그 노드로 이동하여 다시 깊이 탐색을 시작
- 더 이상 갈 수 없을 때까지 이 과정을 반복
✅ 2. 백트래킹(Backtracking)
- 막다른 길에 도착하면, 탐색 경로를 거슬러 올라가(백트래킹) 다른 경로를 찾음
- 이를 통해 아직 방문하지 않은 노드를 탐색
✅ 3. 스택 또는 재귀 사용
- DFS는 후입선출(LIFO) 구조의 스택과 유사하게 동작
- 가장 최근에 방문한 노드의 이웃부터 탐색하기 때문에, 명시적인 스택 자료 구조나 재귀 호출 스택을 사용하여 구현할 수 있음
✅ 4. 최단 경로 보장 불가
- DFS는 깊이를 우선적으로 탐색하기 때문에, 시작 노드에서 목표 노드까지의 최단 경로를 보장하지 않음
- 최단 경로를 찾으려면 일반적으로 BFS(너비 우선 탐색)를 사용
📌 DFS의 단계
✅ 1. 시작점
- 그래프의 임의의 한 노드에서 탐색을 시작
✅ 2. 깊이 우선
- 현재 노드와 연결된 방문하지 않은 노드가 있다면, 그 노드로 이동하고 다시 그 노드에서 탐색을 시작
- 이 과정을 더 이상 갈 곳이 없을 때까지 반복
✅ 3. 백트래킹
- 더 이상 방문할 노드가 없는 막다른 길에 도착하면, 이전 노드로 되돌아가(Backtrack) 아직 방문하지 않은 다른 노드가 있는지 확인
✅ 4. 반복
- 모든 노드를 방문할 때까지 이 과정을 반복
이 과정에서 방문했던 노드를 다시 방문하지 않기 위해 방문 여부를 기록하는 배열이나 리스트를 사용
❗ DFS의 구현
✅ 1. 재귀 호출을 이용한 구현
- 가장 직관적인 방법
- 함수가 자기 자신을 호출하는 재귀적인 특성을 활용하여 깊이 우선 탐색을 쉽게 구현할 수 있음
✅ 2. 스택 자료 구조를 이용한 구현
-
재귀 호출 없이 명시적인 스택(Stack)을 사용하여 DFS를 구현할 수도 있음
- 시작 노드르 스택에 넣고 방문 처리
- 스택이 빌 때까지 다음 과정 반복
- 스택에서 노드를 하나 꺼냄
- 꺼낸 노드와 연결된 방문하지 않은 노드가 있다면 그 노드를 넣고 방문 처리
- 스택의 LIFO(Last-In, First-Out) 특성 덕분에 가장 최근에 넣은 노드(가장 깊은 노드)부터 탐색하게 되어 DFS가 구현
⚠️ DFS의 장단점
✅ 장점
- 간단한 구현: 특히 재귀를 이용하면 코드가 매우 간결해짐
- 메모리 효율성: 너비 우선 탐색(BFS)에 비해 메모리 사용량이 적음. 한 경로를 탐색하는 동안의 노드들만 스택에 저장하면 되기 때문
- 해 찾기: 깊은 경로에 해답이 있는 경우, BFS보다 빠르게 해를 찾을 수 있음
❌ 단점
-
비효율성: 해답이 시작 노드 근처에 있거나, 탐색 트리의 깊이가 매우 깊은 경우 비효율적일 수 있음. 무한 루프에 빠질 수도 있음
-
최단 경로 보장 X: 시작 노드에서 목표 노드까지의 최단 경로를 보장하지 않음. 최단 경로를 찾으려면 보통 BFS 사용
-
시간 및 공간 복잡도
- 시간 복잡도: 그래프의 모든 노드와 간선을 한 번씩 방문하므로, 인접 리스트로 구현했을 때 , 인접 행렬로 구현했을 때 가 됨 (V는 노드의 수, E는 간선의 수)
- 공간 복잡도: 스택에 저장되는 노드의 수가 최대 그래프의 깊이와 비례하므로 가 됨
📝 예제
모든 노드 방문하기
A -- B
| |
C -- D노드 A는 노드 B와 노드 C에 연결
노드 B는 노드 A와 노드 D에 연결
노드 C는 노드 A와 노드 D에 연결
노드 D는 노드 B와 노드 C에 연결
✅ 1. 재귀 DFS
'A'에서 시작해 'A'와 연결된 'B'로 가고, 다시 'B'와 연결된 'D'로 깊숙이 들어감. 'D'에서 더 이상 갈 곳이 없으면 'B'로 돌아와 'C'로 가는 경로를 찾음. 결과적으로 A -> B -> D -> C 순서로 모든 노드를 방문.
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
def dfs_recursive(graph, start_node, visited):
# 현재 노드 방문 처리
visited.add(start_node)
print(start_node, end=' ')
# 현재 노드와 연결된 모든 노드 탐색
for neighbor in graph[start_node]:
# 아직 방문하지 않았다면 재귀 호출
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
# 실행 예제
print("재귀 DFS 결과:", end=' ')
visited = set()
dfs_recursive(graph, 'A', visited)
# 출력: 재귀 DFS 결과: A B D C
✅ 2. 스택을 이용한 DFS
재귀와 동일한 원리로 동작하지만, 명시적인 스택을 사용하여 깊이를 탐색. 스택의 LIFO(Last-In, First-Out) 특성을 이용해 가장 최근에 넣은 노드(가장 깊은 노드)부터 꺼내어 탐색. 예시 코드에서는 A -> C -> D -> B 순서로 노드를 방문.
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
def dfs_stack(graph, start_node):
visited = set()
stack = [start_node]
while stack:
# 스택의 맨 위 노드를 꺼냄 (가장 마지막에 넣은 노드)
node = stack.pop()
if node not in visited:
# 방문 처리
visited.add(node)
print(node, end=' ')
# 인접 노드들을 스택에 넣음.
# 스택의 특성상 마지막에 넣은 노드부터 탐색하게 됨
# 여기서는 C가 B보다 먼저 탐색되도록 순서를 뒤집음 (A의 인접 노드: ['B', 'C'])
# 순서는 결과에 영향을 미치므로 구현에 따라 다를 수 있음
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
# 실행 예제
print("\n스택 DFS 결과:", end=' ')
dfs_stack(graph, 'A')
# 출력: 스택 DFS 결과: A C D B🔎 DFS의 주요 활용 예시
DFS는 단순히 노드를 방문하는 것 외에 다양한 문제 해결에 활용될 수 있음
✅ 1. 그래프 연결 요소 찾기
DFS는 서로 연결된 노드들의 집합, 즉 연결 요소(Connected Components)를 찾는 데 매우 효과적
-
동작 방식
- 탐색을 시작한 노드와 방문한 노드를 기록하는 두 가지의 종류의 배열(또는 집합) 사용
- DFS 탐색 중 현재 노드와 연결된 다음 노드가 이미 '탐색 중인 경로에 포함된 노드(재귀 호출 스택에 있는 노드)'라면, 이는 사이클이 존재한다는 뜻
- DFS가 한 노드의 모든 이웃을 탐색하고 돌아올 때(백트래킹), 해당 노드를 '탐색 중인 경로'에서 제외
-
ex) A -> B -> C -> A와 같이 연결된합니다. C에서 다시 A를 방문하려 할 때, A는 이미 '탐색 중인 경로'에 포함되어 있으므로 사이클이 감지됨.
✅ 2. 사이클(Cycle) 감지
DFS는 그래프에 순환(Cycle) 구조가 있는지 여부를 감지하는 데 유용
-
동작 방식
- 탐색을 시작한 노드와 방문한 노드를 기록한느 두가지 종류의 배열(또는 집합) 사용
- DFS 탐색 중 현재 노드와 연결된 다음 노드가 이미 '탐색 중인 경로에 포함된 노드(재귀 호출 스택에 있는 노드)'라면, 이는 사이클이 존재한다는 뜻
- DFS가 한 노드의 모든 이웃을 탐색하고 돌아올 때(백트래킹), 해당 노드를 '탐색 중인 경로'에서 제외
-
ex) A -> B -> C -> A와 같이 연결된 그래프에서, A에서 DFS를 시작하여 B를 거쳐 C로 이동. C에서 다시 A를 방문하려 할 때, A는 이미 '탐색 중인 경로'에 포함되어 있으므로 사이클이 감지됨.
✅ 3. 위상 정렬(Topological Sort)
방향성 비순환 그래프(DAG, Directed Acyclic Graph)의 노드들을, 모든 간선이 정렬된 순서를 따르도록 순서대로 나열하는 것을 위상 정렬이라고 함. DFS를 이용하면 이를 효율적으로 수행할 수 있음.
-
동작 방식
- 그래프의 모든 노드에 대해 DFS를 실행
- FS 탐색이 끝나서 '더 이상 방문할 노드가 없는' 상태가 되면, 해당 노드를 결과 목록의 가장 앞쪽에 추가 (또는 리스트의 맨 뒤에 추가한 뒤, 리스트를 뒤집는다.)
- 이 과정을 반복하면, 모든 선행 노드가 후행 노드보다 먼저 오게 되는 순서를 얻을 수 있음
-
ex) 과목 수강 순서와 같은 문제에 적용할 수 있음. 자료구조 과목을 수강해야 알고리즘 과목을 들을 수 있다면, 위상 정렬을 통해 자료구조가 알고리즘보다 먼저 오도록 순서를 정할 수 있음. DFS는 가장 깊숙이 있는(가장 후행하는) 노드부터 처리하기 때문에 이 문제를 해결하기에 적합.
✅ 4. 미로 찾기
미로의 한 지점에서 시작해 막다른 길에 다다를 때까지 한 방향으로 깊게 탐색하는 과정은 DFS와 동일
✅ 5. 백트래킹(Backtracking)
'N-Queens', 스도쿠, 조합 문제 등 해를 찾기 위해 모든 가능성을 탐색하다가 해가 될 수 없는 경로이면 되돌아오는 모든 종류의 문제에 DFS가 기본 원리로 활용
