10-1. DFS (Depth-First Search)

10-1. DFS (Depth-First Search)

1. DFS란?

깊이 우선 탐색

• 말 그대로 한 방향으로 끝까지 파고들었다가,
• 더 갈 데 없으면 이전으로 돌아와서 다른 길을 탐색하는 방식

💡 동작 방식

예시 그래프:

    1
   / \
  2   3
 /     \
4       5

1 → 2 → 4 → (끝) → 백 → 3 → 5

→ 깊이 우선으로 계속 들어감 → 더 이상 없으면 백트래킹

---

2. DFS의 기본 구조

def dfs(node):
	visited[node] = True
	for neighbor in graph[node]:
		if not visited[neighbor]:
			dfs(neighbor)

---

3. 그래프 표현 방법

📌 인접 리스트 방식 (가장 많이 씀)

graph = {
	1: [2, 3],
	2: [4],
	3: [5],
	4: [],
	5: []
}

또는

graph = [[] for _ in range(n+1)]
graph[1].append(2)
graph[1].append(3)
...

---

4. DFS 2가지 구현 방법

방식	특징
재귀	코드 짧고 간결함
스택 기반 반복문	재귀 깊이가 깊을 때 필요 (stack 사용)

4.1 DFS 예제 1 – 간단한 그래프 탐색 (재귀)

def dfs(v):
	visited(v) = True
	print(v, end = ' ')
	for neighbor in graph[v]:
		if not visited[neighbor]:
			dfs[neighor]

graph = {
	1: [2, 3],
	2: [4],
	3: [5],
	4: [],
	5: []
}

visited = [False] * 6
dfs(1)

'''
1 [False, True, False, False, False, False] 
2 [False, True, True, False, False, False] 
4 [False, True, True, False, True, False] 
3 [False, True, True, True, True, False] 
5 [False, True, True, True, True, True]

    1
   / \
  2   3
 /     \
4       5
'''

4.2 DFS 예제 2 - 간단한 그래프 탐색 (스택)

def dfs_stack(start):
	stack = [start]
	while stack:
		v = stack.pop()
		if not visited[v]:
			visited[v] = True
			print(v, end = ' ')
			# 인접 노드를 역순으로 넣어야 순서 보장됨 
			for neighbor in reversed(graph[v]):
					stack.append(neighbor)

graph = {
	1: [2, 3],
	2: [4, 5],
	3: [],
	4: [],
	5: []
}

visited = [False] * 6
dfs_stack(1)

---

6. DFS는 어디에 쓰나?

분야	설명
그래프 탐색	노드 방문 여부 판단
연결 요소 찾기	섬의 개수, 친구 관계, 네트워크
백트래킹 문제	N-Queen, 조합, 미로 탐색
사이클 판별	방향/무방향 그래프의 루프 존재 여부