깊이 우선 탐색(DFS, Depth First Search)
깊이 우선 탐색이라는 알고리즘에 대해 알아보려고 합니다. 일반적으로 DFS 알고리즘을 구현할때는 스택을 이용하고, 트리 혹은 그래프 같은 자료구조에서 데이터를 탐색할 때 사용하는 알고리즘 입니다. 나중에 알아볼 너비 우선 탐색이라는 비슷한 알고리즘이 있는데, 다음 게시물에서 다루도록 하겠습니다.
깊이 우선 탐색 알고리즘은 한마디로 더 나아갈 길이 보이지 않을 만큼 깊게 들어가는 특징을 지니고 있으며, 더 깊게 들어갈 경로가 존재하지 않으면 이전의 위치로 돌아온 뒤 다른 경로를 선택해서 움직입니다.
(그래프를 첨부하고 싶은데 어떻게 첨부하는지 모르겠네요 ㅠㅠ)
연습장 꺼내신 후 직접 그려보시면 이해가 더 빠르실거에요...ㅎㅎㅎ
그래프를 간략하게 노드들만 나타내보도록 하겠습니다 각 노드간은 연결되어 있는 상태라고 가정할게요. 즉 각 Vertex들을 잇는 Edge는 모두 연결되어 있는 상태입니다!
|
|
1 |
|
|
|
|
2 |
|
|
3 |
|
4 |
|
5 |
6 |
|
7 |
|
|
8 |
|
|
|
시작 Vertex(노드)는 1에서 부터 시작하겠습니다. 앞에서 언급했듯이 계속 탐색한 후 길이 없으면 되돌아 간 후 다른 경로를 선택하는 알고리즘 입니다.
방문 순서는 1 -> 2 -> 4 -> 8 -> 5 -> 6 -> 3 -> 7 로 진행되겠죠. 그렇다면 여기서 이론은 끝! DFS 알고리즘을 직접 구현해보도록 하겠습니다. 먼저 코드로 구현하기 전에 Vertex간 관계를 나타내기 위해 인접행렬을 사용하겠습니다. 인접행렬은 그래프에서 각 정점의 인접관계를 나타내는 행렬입니다. (간단한 내용이니 궁금하시면 검색해보세요!)
※ 인접행렬
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
C++로 구현한 단순 DFS 알고리즘 입니다.
#include <iostream> int vertex; //정점 갯수 int map[30][30], visit[30]; // map - 상호간 연결을 나타냄 // visit - 방문 여부 void DFS(int t_vertex); using namespace std; int main() { int sVertex; // Start Vertex int v1, v2; cin>>vertex>>sVertex; while(true) { cin>>v1>>v2; if(v1 == -1 && v2 == -1) //무한루프 방지 break; map[v1][v2] = map[v2][v1] = 1; // vertex 상호간 연결 } DFS(sVertex); return 0; } void DFS(int t_vertex) { visit[t_vertex] = 1; // visit vertex for(int i=1; i<=vertex; i++){ if(map[t_vertex][i] == 1 && !visit[i]) { cout<<t_vertex<<"에서 "<<i<<"로 이동합니다"<<endl; DFS(i); } } } |