개념
깊이 우선 탐색 (Depth-First Search)
DFS는 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 시작 노드에서부터 이웃한 노드를 계속해서 탐색하다가 더 이상 탐색할 수 없는 상황에 이르면 이전에 탐색한 노드로 돌아와 다른 경로를 탐색합니다. 이 과정을 반복하여 모든 노드를 방문합니다. 일반적으로 재귀적인 방법으로 구현되며, 스택(Stack) 자료구조를 사용하여 탐색 경로를 저장합니다. DFS는 깊은 경로를 우선적으로 탐색하기 때문에 그래프의 구조에 따라서는 모든 노드를 탐색하지 못할 수도 있습니다.
작동 방식
- 시작 노드를 방문 처리합니다.
- 시작 노드와 인접한 노드들 중에서 방문하지 않은 노드를 선택합니다.
- 선택한 노드를 스택에 넣고 방문 처리합니다.
- 선택한 노드를 현재 노드로 설정하고 2단계로 돌아갑니다.
- 만약 선택한 노드와 인접한 모든 노드들이 이미 방문되었거나 선택할 수 있는 노드가 없다면, 스택에서 하나의 노드를 꺼내고 해당 노드를 현재 노드로 설정합니다.
- 5단계를 스택이 비어있을 때까지 반복합니다.
이 작동 방식을 좀 더 구체적으로 설명하면 다음과 같습니다.
- 스택은 LIFO(Last-In, First-Out) 원칙에 따라 노드들을 저장하는 자료구조입니다. 방문할 노드를 스택의 맨 위에 삽입하고, 노드를 꺼낼 때는 스택의 맨 위에서 꺼냅니다.
- 시작 노드를 방문 처리하고 스택에 넣습니다.
- 스택이 비어있지 않은 동안 다음을 반복합니다
- 스택의 맨 위에 있는 노드를 꺼냅니다.
- 해당 노드를 방문 처리합니다.
- 해당 노드와 인접한 미방문 노드를 선택합니다.
- 선택한 노드를 스택에 넣고 방문 처리합니다.
- 반복이 종료되면 모든 노드를 방문했으며, 방문한 순서대로 결과를 반환하거나 원하는 동작을 수행합니다.
특징
-
스택(Stack)이나 재귀 호출: DFS는 스택 자료구조를 활용하거나 재귀 호출을 통해 구현됩니다. 스택을 사용하면 현재 경로를 기억하고 이전 경로로 돌아갈 수 있으며, 재귀 호출을 통해 코드의 간결성을 높일 수 있습니다.
-
깊이 우선 탐색 특성: DFS는 한 경로를 최대한 깊이 탐색하는 특성을 가지고 있습니다. 따라서 그래프의 깊은 부분을 먼저 탐색하고, 노드를 방문한 순서대로 스택에 저장됩니다.
-
그래프 탐색에서 사용되는 자주 쓰이는 알고리즘: DFS는 그래프 탐색에 많이 사용되며, 연결 요소, 사이클 찾기, 위상 정렬 등 다양한 그래프 알고리즘에 활용됩니다.
-
재귀적 구조: DFS는 보통 재귀적인 구조로 구현됩니다. 현재 노드에서 이웃한 노드를 재귀적으로 호출하여 탐색을 진행하고, 탈출 조건에 도달하면 이전 호출로 돌아가며 탐색을 계속합니다.
-
모든 경로 탐색: DFS는 그래프의 모든 경로를 탐색하기 때문에 완전 탐색(Exhaustive Search)에 유리합니다. 그래프에서 시작 노드에서 도달 가능한 모든 노드를 방문하며, 특정 조건을 만족하는 경로를 찾을 수 있습니다.
-
추가적인 메모리 사용: DFS는 스택을 사용하므로 추가적인 메모리가 필요합니다. 그래프의 깊이에 따라 스택의 크기가 커지기도 합니다. 따라서 깊은 그래프에서는 스택 오버플로우 등의 문제가 발생할 수 있습니다.
예시
-
그래프 탐색: DFS는 그래프에서 모든 노드를 탐색하거나 특정 노드 간의 경로를 찾는 데 사용됩니다. 그래프의 인접 노드를 재귀적으로 방문하여 탐색하며, 필요한 정보를 수집하거나 조건에 맞는 경로를 찾을 수 있습니다.
-
백트래킹: DFS는 백트래킹 알고리즘의 핵심이며, 조합 탐색, 제약 충족 문제 등에서 활용됩니다. 선택 단계에서 가능한 모든 경우를 재귀적으로 탐색하고, 제약 조건을 만족하지 않는 경우 해당 선택을 폐기하고 다른 선택을 진행합니다.
-
그래프 알고리즘: DFS는 그래프의 사이클을 찾는 데 사용될 수 있습니다. 사이클 여부를 판단하기 위해 재귀 호출을 통해 그래프를 탐색하면서 방문한 노드를 기록하고, 사이클이 발견되면 해당 정보를 반환할 수 있습니다.
-
미로 찾기: DFS를 사용하여 미로에서 출발점부터 도착점까지의 경로를 찾을 수 있습니다. 각 위치에서 가능한 이동 방향을 재귀적으로 탐색하고, 도착점에 도달하는 경로를 발견하면 반환합니다.
-
그 외: DFS는 위상 정렬, 연결 요소 탐색, 감염병 전파 모델링 등 다양한 문제에서 활용될 수 있습니다. 탐색 순서나 탐색 경로에 따라 다양한 정보를 얻거나 조작할 수 있습니다.
예시를 위해 다음과 같은 그래프를 가정해 보겠습니다.
A
/ | \
B C D
/ \ / \
E F G H초기 상태:
시작 정점: A
방문한 정점: []
시작 정점 A 방문:
방문한 정점: [A]
A의 이웃 정점 B 선택:
방문한 정점: [A, B]
B의 이웃 정점 E 선택:
방문한 정점: [A, B, E]
E의 이웃 정점이 없으므로, B로 돌아갑니다.
B의 다음 이웃인 F 선택:
방문한 정점: [A, B, E, F]
F의 이웃 정점이 없으므로, B로 돌아갑니다.
B의 이웃 정점이 모두 탐색되었으므로, A로 돌아갑니다.
A의 다음 이웃인 C 선택:
방문한 정점: [A, B, E, F, C]
C의 이웃 정점인 G 선택:
방문한 정점: [A, B, E, F, C, G]
G의 이웃 정점이 없으므로, C로 돌아갑니다.
C의 다음 이웃인 D 선택:
방문한 정점: [A, B, E, F, C, G, D]
D의 이웃 정점인 H 선택:
방문한 정점: [A, B, E, F, C, G, D, H]
H의 이웃 정점이 없으므로, D로 돌아갑니다.
D의 이웃 정점이 모두 탐색되었으므로, A로 돌아갑니다.깊이 우선 탐색은 현재 정점에서 깊게 들어가면서 탐색하기 때문에 그래프의 깊은 부분을 우선적으로 탐색합니다. 이 알고리즘은 스택(Stack) 자료구조를 사용하여 구현할 수 있습니다. 또는 재귀 함수를 사용하여 깊이 우선 탐색을 구현할 수도 있습니다.
