재귀함수, stack을 이용한 DFS 구현
DFS(Depth-First-Search) 깊이 우선 탐색?
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
해석해보면,
- 트리 / 그래프 자료구조를 순회하거나 탐색할 때 사용한다.
- 루트 노드에서 시작하여 가능한 깊이 탐색한 후에 더 이상 방문하지 않은 인접한 노드가 없을 때에 돌아간다.
- 그래프의 경우에는 임의의 노드를 루트 노드로 사용한다.
DFS의 특징 / 사용하는 경우
- 탐색 속도 자체는 BFS보다 느리다.
- 모든 노드를 방문해야 하는 경우에 활용한다.
- 경로에 조건이 있을 때에 사용한다. 한 노드에서 다른 노드로 가는 경로에 어떤 조건이 주어진다면 DFS를 사용해야 한다.
- 최단 거리를 구할 때에 적합하지 못하다. 경로가 여러 개인 그래프에서 처음에 발견한 해가 최적이 아닐 수 있지만, DFS는 그 경로를 해로 출력한다. 최단 거리는 BFS!
활용 문제
실습 코드
1. stack을 이용한 구현
루트 노드와 연결된 하나의 노드를 stack에 넣고, 또 그 노드와 연결된 하나의 노드를 넣는 과정을 반복한다. 더 이상 연결된 (방문하지 않은) 노드가 없다면, 그 노드를 pop하여 이전 노드로 돌아가서 다시 인접한 노드가 있는지 확인하는 방식으로 구현을 한다. 위의 예시에서 1을 루트 노드로 하여 모든 노드를 순회할 때까지 stack에 삽입/삭제되는 순서는 아래 그림과 같다.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<int> v[10] = { {}, {2, 3}, {1, 3, 4, 5},
{1, 2, 6, 7}, { 2, 8 }, { 2, 9 }, { 3 }, { 3 }, { 4 }, { 5 } };
bool isVisited[9];
int main(void) {
stack<int> s;
cout << "** node" << 1 << " visited! **" << endl;
cout << "push 1" << endl;
s.push(1);
isVisited[1] = true;
while (!s.empty()) {
// if the node has (unvisited) connected node(s)
bool isConnected = false;
int cur_node = s.top();
// search all connected nodes
for (auto i = v[cur_node].begin(); i != v[cur_node].end(); i++) {
// if the node has a unvisited & connected node(s)
if (!isVisited[*i]) {
isConnected = true;
cout << "** node" << *i << " visited! **" << endl;
cout << "push " << *i << endl;
s.push(*i);
isVisited[*i] = true;
break;
}
}
// no more unvisited & connected node
if (!isConnected) {
s.pop();
cout << "pop" << cur_node << endl;
}
}
return 0;
}
[실행 결과]
push 2
** node3 visited! **
push 3
** node6 visited! **
push 6
pop6
** node7 visited! **
push 7
pop7
pop3
** node4 visited! **
push 4
** node8 visited! **
push 8
pop8
pop4
** node5 visited! **
push 5
** node9 visited! **
push 9
pop9
pop5
pop2
pop1
[comment]
방문하지 않은 인접한 노드를 발견하면 탐색을 멈추고 새로운 노드에 대한 탐색으로 넘어가도록 for문에 break을 넣어서 구현했다. 그리고 만약 인접한 노드가 없다면, 그 노드를 pop한 후 top 노드에 대한 탐색을 하도록 했다. stack에 원소가 삽입/삭제되는 과정을 보기 위해 push와 pop이 실행될 때 원소를 출력해보았다.
https://github.com/choiiis/1d-1c/blob/master/DFS_stack2.cpp
2. 재귀함수를 이용한 구현
한 노드에서 인접한 노드를 찾고, 그 노드에 대해서 또 인접한 노드를 찾을 때에 재귀함수를 활용하여 구현한 방식이다. 더 이상 방문할 노드가 없으면 함수를 종료하고 호출했던 함수로 돌아가게 된다.
#include <iostream>
#include <vector>
using namespace std;
vector<int> v[10] = { {}, {2, 3}, {1, 3, 4, 5},
{1, 2, 6, 7}, { 2, 8 }, { 2, 9 }, { 3 }, { 3 }, { 4 }, { 5 } };
bool isVisited[9];
void dfs(int cur_node) {
cout << "cur node : " << cur_node << endl;
isVisited[cur_node] = true;
for (auto i = v[cur_node].begin(); i != v[cur_node].end(); i++) {
if(!isVisited[*i])
bfs(*i);
}
}
int main(void) {
dfs(1);
}
[실행 결과]
cur node : 1
cur node : 2
cur node : 3
cur node : 6
cur node : 7
cur node : 4
cur node : 8
cur node : 5
cur node : 9
[comment]
for문으로 한 노드의 인접한 노드들을 찾으면서, 찾은 노드에 대해서 재귀함수로 다시 그 노드에 인접한 노드들을 찾는 방식으로 구현했다. 이 과정을 반복하다가, 더 이상 방문할 노드가 없을 때에 재귀함수가 끝나면서 그 함수를 호출했던 함수로 돌아가게 되는 방식이다.
https://github.com/choiiis/1d-1c/blob/master/DFS_recursive.cpp
Reference
Leave a comment