1. 깊이 우선 탐색(DFS)이란?
DFS는 그래프의 모든 노드를 방문하는 방법 중 하나입니다. "깊이 우선"이란 이름에서 알 수 있듯이, 먼저 가장 깊은 곳의 노드를 우선적으로 방문하는 방식을 사용합니다. DFS는 트리나 그래프의 전체 탐색, 연결 요소(Connected Component)의 개수 계산, 싸이클 판별 등 다양한 문제를 해결하는 데 사용됩니다.
DFS는 다음의 단계를 거쳐 진행됩니다.
- 시작 노드를 스택에 넣어주고 방문 처리를 합니다.
- 스택의 최상단 노드에서 아직 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.
2. C++로 DFS 구현하기
DFS는 재귀 함수나 스택을 이용하여 구현할 수 있습니다. C++에서 기본적인 DFS를 구현하는 방법을 먼저 살펴봅시다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #include<bits/stdc++.h> using namespace std; vector<bool> visited; vector<vector<int>> graph; // DFS 함수 정의 void dfs(int node) { visited[node] = true; // 방문 처리 cout << node << ' '; for(int i = 0; i < graph[node].size(); i++) { int next = graph[node][i]; if(!visited[next]) { dfs(next); // 다음 노드 방문 } } } int main() { // 그래프 초기화 int n = 8; // 노드의 수 graph.resize(n); visited.resize(n, false); // 그래프 간선 정보 입력 graph[1].push_back(2); graph[1].push_back(3); graph[2].push_back(4); graph[2].push_back(5); graph[3].push_back(6); graph[3].push_back(7); dfs(1); // DFS 실행 return 0; } | cs |
위의 코드에서 dfs 함수는 시작 노드를 인자로 받아 해당 노드와 연결된 모든 노드를 탐색합니다. 이때, 노드의 방문 여부를 확인하기 위해 visited라는 벡터를 사용하며, 아직 방문하지 않은 노드에 대해 재귀적으로 dfs 함수를 호출합니다.
3. DFS 활용 예제
이제 실제 문제 해결에 어떻게 DFS를 활용하는지 살펴보겠습니다. 두 가지 예제를 통해 DFS를 활용하는 방법을 알아봅시다.
예제 1: 연결 요소의 개수 계산
그래프의 연결 요소란 그래프 내에서 노드들이 서로 연결되어 있는 부분 집합을 말합니다. DFS를 이용하면 간단하게 연결 요소의 개수를 계산할 수 있습니다. 아래 코드를 살펴봅시다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include<bits/stdc++.h> using namespace std; vector<bool> visited; vector<vector<int>> graph; int component = 0; // 연결 요소의 개수 void dfs(int node) { visited[node] = true; for(int i = 0; i < graph[node].size(); i++) { int next = graph[node][i]; if(!visited[next]) { dfs(next); } } } int main() { int n = 8; graph.resize(n); visited.resize(n, false); graph[1].push_back(2); graph[2].push_back(3); graph[4].push_back(5); graph[6].push_back(7); for(int i = 1; i < n; i++) { if(!visited[i]) { dfs(i); component++; } } cout << "Number of connected components: " << component << '\n'; return 0; } | cs |
예제 2: 경로 찾기
DFS는 그래프 내의 두 노드 사이의 경로를 찾는데도 사용됩니다. 아래 코드를 살펴봅시다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include<bits/stdc++.h> using namespace std; vector<bool> visited; vector<vector<int>> graph; vector<int> path; void dfs(int node, int destination) { visited[node] = true; path.push_back(node); if(node == destination) { for(int i = 0; i < path.size(); i++) { cout << path[i] << ' '; } cout << '\n'; } else { for(int i = 0; i < graph[node].size(); i++) { int next = graph[node][i]; if(!visited[next]) { dfs(next, destination); } } } path.pop_back(); visited[node] = false; } int main() { int n = 8; graph.resize(n); visited.resize(n, false); graph[1].push_back(2); graph[1].push_back(3); graph[2].push_back(4); graph[2].push_back(5); graph[3].push_back(6); graph[3].push_back(7); dfs(1, 6); // 경로 찾기 return 0; } | cs |
마치며
DFS는 그래프에서 중요한 탐색 알고리즘 중 하나로, 다양한 문제에 활용될 수 있습니다. 이 글에서는 C++을 이용해 DFS를 간단하게 구현해 보았습니다. 그래프와 DFS에 대한 기본적인 이해를 통해, 이 알고리즘을 실제 문제 해결에 활용하실 수 있기를 바랍니다. 항상 즐거운 코딩 되세요!
댓글 없음:
댓글 쓰기