안녕하세요 기린입니다 :)
오늘은 지난 시간에 이어 깊이 우선 탐색(Depth-Frist Search)에 대해 알아보도록 하겠습니다.
먼저 깊이 우선 탐색이란 말 그대로 보다 깊은 것을 우선적으로 탐색하는 알고리즘입니다. 맹목적으로 각 노드를 탐색할 때 주로 사용되죠. 너비 우선 탐색과는 다르게 큐(Queue)를 사용하지 않고 스택(Stack)이 사용됩니다. 그리고 굳이 스택을 사용하지 않아도 구현이 가능하다는 특징이 있습니다. 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문입니다.
DFS는 맨 처음에 시작 노드(Start Node)를 스택에 삽입하면서 시작합니다. 또한 그와 동시에 시작 노드를 방문했다고 알리는 '방문 처리'를 해주도록 합니다. 방문 처리는 파란색으로 해주도록 하겠습니다.
이제는 DFS는 다음과 같은 간단한 알고리즘에 따라서 작동합니다.
1. 스택의 최상단 노드를 확인합니다.
2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 뺍니다.
위 알고리즘을 계속해서 반복 수행해주시면 됩니다.
스택에 있던 최상단 노드가 1번 노드이므로 인접한 노드 중에서 방문하지 않은 2번 노드를 넣습니다.
이후에 2번 노드의 인접 노드 중 방문하지 않은 노드인 3번 노드를 스택에 넣습니다.
이어서 3번 노드의 인접 노드 중 방문하지 않은 노드인 6번 노드를 스택에 넣습니다.
이어서 6번 노드의 인접 노드 중 방문하지 않은 노드인 7번 노드가 위와 같이 삽입됩니다.
이후에 7번 노드, 6번 노드, 3번 노드는 스택에서 빠져나오게 됩니다. 인접 노드를 전부 방문했으니까요 :) 이후에 2번 노드를 보면 인접 노드이고 아직 방문하지 않은 노드인 4번을 스택에 넣습니다.
결과적으로 4번 노드의 인접 노드인 5번 노드가 스택에 들어가고, 이후에 스택에서 하나씩 노드들이 빠져나오게 됩니다.
위와 같이 스택에서 모두 빠져나오면 깊이 우선 탐색의 방문 경로는 1 - 2 - 3 - 6 - 7 - 4 - 5 로 됩니다. 소스코드를 보실게요
#include <iostream>
#include <vector>
using namespace std;
// visit array
int c[7];
vector<int> a[8];
void dfs(int x) {
if (c[x]) return;
c[x] = true;
cout << x << ' ';
for (int i = 0; i < a[x].size(); i++) {
int y = a[x][i];
dfs(y);
}
}
int main(void) {
// Connect 1 and 2
a[1].push_back(2);
a[2].push_back(1);
// Connect 1 and 3
a[1].push_back(3);
a[3].push_back(1);
// Connect 2 and 3
a[2].push_back(3);
a[3].push_back(2);
// Connect 2 and 4
a[2].push_back(4);
a[4].push_back(2);
// Connect 2 and 5
a[2].push_back(5);
a[5].push_back(2);
// Connect 3 and 6
a[3].push_back(6);
a[6].push_back(3);
// Connect 3 and 7
a[3].push_back(7);
a[7].push_back(3);
// Connect 4 and 5
a[4].push_back(5);
a[5].push_back(4);
// Connect 6 and 7
a[6].push_back(7);
a[7].push_back(6);
// Perform DFS
dfs(1);
return 0;
}
DFS 또한 DFS 자체로는 큰 의미가 없고 DFS를 활용해서 문제를 해결하고자 하는 것에 주안점이 있으므로 작동 원리에 대해서만 빠삭하게 이해하시면 됩니다. 또한 스택을 직접 사용하지 않고 재귀 함수를 이용해 간략하게 구현해봤으니 참고 하시면 될 것 같습니다.
자 그럼 즐거운 코딩하세요 :)
문의: ralla0405@gmail.com
