Depth First Search (깊이 우선 탐색)
개요
깊이 우선 탐색(DFS, Depth First Search)은 그래프 탐색 알고리즘 중 하나로, 한 노드를 시작으로 연결된 노드를 따라 최대한 깊이 탐색한 후, 더 이상 갈 수 없으면 다시 돌아와 다른 경로를 탐색하는 방식이다.
그래프의 탐색
DFS는 그래프 탐색 방법 중 하나로, 모든 노드를 방문하고자 할 때 사용된다. 그래프에서 노드를 하나 선택하고, 연결된 노드를 따라가며 최대한 깊이 탐색하는 것이 특징이다.
깊이를 우선한다는 것의 의미
깊이 우선 탐색은 한 경로로 최대한 깊이 탐색한 후 더 이상 나아갈 수 없을 때 다른 경로를 찾는다. 이를 재귀적으로 반복하며 그래프의 모든 노드를 방문할 수 있다.
함수 DFS(노드 v, 그래프 G, 방문 여부 visited):
방문 여부 visited[v] = 참 // 현재 노드를 방문했다고 표시
출력(노드 v) // 현재 노드를 출력
// v에 인접한 모든 노드에 대해 반복
for 인접 노드 u in G[v]:
만약 visited[u] == 거짓 이라면
DFS(노드 u, 그래프 G, 방문 여부 visited) // 인접 노드에 대해 재귀 호출
C++
복사
스택과 DFS
자료 구조로 보자면 스택 자료형이 DFS와 큰 연관이 된다.
•
스택의 동작 원리:
◦
스택은 후입선출(LIFO, Last In First Out) 방식으로 동작하는 자료구조이다. 즉, 나중에 삽입된 데이터가 먼저 삭제된다.
◦
DFS에서는 한 정점에서 출발해 가능한 깊이까지 계속 탐색하다가 더 이상 갈 곳이 없으면 직전의 정점으로 되돌아가는 방식으로 작동한다. 이 방식은 스택의 후입선출 원리와 일치한다.
•
DFS의 동작 방식:
◦
DFS는 한 정점에서 출발해 해당 정점의 모든 인접 정점을 방문하고, 다시 그 인접 정점에서 깊이 들어가는 방식이다. 만약 더 이상 방문할 정점이 없으면 이전에 탐색한 정점으로 돌아가야 한다.
◦
이때 스택이 사용된다. 탐색할 정점을 스택에 넣고, 그 정점을 탐색한 후 다시 스택에서 빼는 과정으로 DFS를 구현할 수 있다.
•
스택을 이용한 DFS의 구현:
DFS는 재귀 함수로도 구현될 수 있지만, 이를 반복문을 사용해 구현하려면 스택이 필요하다. 스택에 현재 탐색 중인 경로를 저장하고, 다음 정점을 방문할 때마다 그 정점을 스택에 넣는다. 탐색이 끝나면 스택에서 해당 정점을 제거하면서 탐색을 진행한다.
DFS(시작 정점 s):
스택 S를 빈 상태로 초기화
시작 정점 s를 S에 삽입
s를 방문 처리
while S가 비어 있지 않으면:
정점 u = S에서 꺼냄
u와 인접한 모든 정점 v에 대해:
만약 v를 방문하지 않았다면:
v를 S에 삽입
v를 방문 처리
Python
복사
예제
다음은 DFS로 그래프를 탐색하는 예시이다. 그래프는 각 노드가 숫자로 이루어져 있으며, 각 노드는 서로 연결된 상태이다.
•
예시 그래프
1
/ \\
2 3
| |
4 5
Plain Text
복사
이 그래프에서 DFS는 다음과 같은 순서로 노드를 방문한다:
1 -> 2 -> 4 -> 3 -> 5
•
각 숫자는 노드를 의미하며, / 등의 선은 간선을 의미한다.
•
1번에서부터 시작되어, 왼쪽에 있는 2 를 탐색한 뒤, 갈 수 있는 최대한인 4 를 탐색한다.
•
이후 다시 갈 수 없으므로, 가지 않은 3으로 들어가고 마지막으로 갈 수 있는 5를 들어가서 탐색을 마친다.
트리 구조와 DFS
트리 구조에서 전위 순회를 일반화한 것이 DFS이다.
DFS 코드 (C++)
코드를 구현하는데 있어 가장 중요한 것은 visited 라는 변수이다. 이미 다녀온 노드들의 정보를 갖고 있기에 구현에 있어 필수적으로 사용된다.
아래 코드에서는 기본적으로 노드는 인덱스와 같다고 취급한다. 이 말인 즉슨 노드가 어떤 데이터나 객체의 형태가 아니라, 인덱스로 취급되므로 인접행렬만 있으면 바로 할 수 있다.
그래서 복잡할 것 없이 vector<vector<int>> graph(numNodes); 이 줄 하나에서 볼 수 있듯이 2차원 배열만 가지고 바로 선언한 것이다.
아래 코드는 인접리스트로 구현한 방식이다.
#include <iostream>
#include <vector>
using namespace std;
void DFS(int node, vector<vector<int>>& graph, vector<bool>& visited) {
visited[node] = true;
cout << node << " ";
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
DFS(neighbor, graph, visited);
}
}
}
int main() {
int numNodes = 6;
vector<vector<int>> graph(numNodes);
graph[1] = {2, 3};
graph[2] = {4};
graph[3] = {5};
vector<bool> visited(numNodes, false);
DFS(1, graph, visited);
return 0;
}
C++
복사
인접행렬로 구하면 다음과 같다.
•
첫 번째와 두번째 큰 차이는 없다. 예시일 뿐이다.
#include <vector>
#include <iostream>
using namespace std;
int SENTINEL_VALUE = -1;
int numNodes = 5;
void DFS(int node, vector<vector<int>>& graph, vector<bool>& visited) {
visited[node] = true;
cout << node << " ";
for (int i = 1; i <= numNodes; i++) {
if (graph[node][i] != SENTINEL_VALUE) // if vertexes are connected
{
if (!visited[i]) {
DFS(i, graph, visited);
}
}
}
}
int main() {
// 인접 행렬을 0으로 초기화
vector<vector<int>> graph(numNodes + 1, vector<int>(numNodes + 1, SENTINEL_VALUE));
// 노드 연결을 행렬에 반영 (양방향이 아니면 한쪽만 추가)
graph[1][2] = 1;
graph[1][3] = 1;
graph[2][4] = 1;
graph[3][5] = 1;
vector<bool> visited(numNodes, false);
DFS(1, graph, visited);
return 0;
}
C++
복사
#include <iostream>
#include <vector>
using namespace std;
void DFS(int node, vector<vector<int>>& graph, vector<bool>& visited) {
visited[node] = true;
cout << node << " ";
for (int i = 1; i < graph.size(); i++) {
if (graph[node][i] == 1 && !visited[i]) { // 연결된 노드가 있고, 방문하지 않았다면
DFS(i, graph, visited);
}
}
}
int main() {
int numNodes = 6;
// 인접 행렬을 초기화 (6x6 행렬, 0으로 초기화)
vector<vector<int>> graph(numNodes, vector<int>(numNodes, 0));
// 노드 간의 연결 설정 (인접 행렬 방식)
graph[1][2] = 1;
graph[1][3] = 1;
graph[2][4] = 1;
graph[3][5] = 1;
vector<bool> visited(numNodes, false);
// DFS 실행 (시작 노드는 1)
DFS(1, graph, visited);
return 0;
}
C++
복사
DFS 코드 (Python)
인접리스트 기반
인접 행렬 기반
스택 기반 DFS 구현
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
void DFS(int start, vector<vector<int>>& adjList, vector<bool>& visited) {
stack<int> s;
s.push(start);
visited[start] = true;
while (!s.empty()) {
int current = s.top();
s.pop();
cout << current << " ";
for (int neighbor : adjList[current]) {
if (!visited[neighbor]) {
s.push(neighbor);
visited[neighbor] = true;
}
}
}
}
int main() {
int n = 6; // 노드 수
vector<vector<int>> adjList(n);
adjList[0] = {1, 3};
adjList[1] = {0, 2, 4};
adjList[2] = {1};
adjList[3] = {0, 4};
adjList[4] = {1, 3, 5};
adjList[5] = {4};
vector<bool> visited(n, false);
DFS(0, adjList, visited);
return 0;
}
C++
복사
def dfs_stack(start, adj_list):
visited = [False] * len(adj_list)
stack = [start]
visited[start] = True
while stack:
current = stack.pop() # 스택의 맨 위에서 꺼냄 (LIFO)
print(current, end=' ') # 방문한 노드 출력
# 인접한 노드들을 확인
for neighbor in adj_list[current]:
if not visited[neighbor]:
stack.append(neighbor)
visited[neighbor] = True
# 예시 인접 리스트 (그래프)
adj_list = [
[1, 3], # 0번 노드와 인접한 노드들
[0, 2, 4], # 1번 노드와 인접한 노드들
[1], # 2번 노드와 인접한 노드들
[0, 4], # 3번 노드와 인접한 노드들
[1, 3, 5], # 4번 노드와 인접한 노드들
[4] # 5번 노드와 인접한 노드들
]
dfs_stack(0, adj_list) # 시작 노드 0에서 DFS 탐색 시작
Python
복사
인접 행렬 vs 인접 리스트
DFS(깊이 우선 탐색)을 인접 행렬과 인접 리스트로 구현할 때, 성능 차이가 발생할 수 있다.
1. 인접 행렬로 구현한 DFS 성능
2. 인접 리스트로 구현한 DFS 성능
•
성능 비교 요약
구분 | 인접 행렬 | 인접 리스트 |
시간 복잡도 | O(n^2) | O(n + m) |
공간 복잡도 | O(n^2) | O(n + m) |
장점 | 노드 간 연결 여부 즉시 확인 가능 | 메모리 효율적, 실제 연결된 노드만 탐색 |
단점 | 메모리 소모가 크고 탐색 시간이 오래 걸림 | 특정 노드와 연결 여부 확인 시 느림 |
•
인접 행렬은 작은 그래프나 노드가 매우 밀집되어 있는 그래프에서는 유리할 수 있다. 연결 여부를 즉시 확인할 수 있기 때문에 일부 경우에서 빠르게 처리할 수 있다.
•
인접 리스트는 큰 그래프에서 훨씬 효율적이다. 특히 노드가 많은 경우 메모리 사용량을 절약할 수 있고, 탐색도 실제로 연결된 노드만 확인하므로 더 빠르게 진행된다.
따라서 인접 행렬은 밀집 그래프(조밀 그래프)에서, 인접 리스트는 희소 그래프에서 더 효율적이라고 할 수 있다.
요약
•
깊이 우선 탐색은 한 경로로 최대한 깊이 탐색한 후 다른 경로로 이동하는 방식으로 그래프의 모든 노드를 방문하는 탐색 알고리즘이다.
•
DFS는 재귀문으로 쉽게 구현이 가능하다.
참고로,
파이썬에서의 2차원 배열 선언 방식 중에 두 가지를 쓸 수 있다.
graph = [[0 for _ in range(node_num+1)] for _ in range(node_num+1)]
Python
복사
for i in range(rows):
array.append([0] * cols)
Python
복사
REFERENCES
•
주우석, 2015, C/C++로 배우는 자료구조론, 한빛미디어
Written by Changyu Lee