[C++] 깊이 우선 탐색(DFS : Depth First Search)

이번 시간에는 깊이 우선 탐색에 대해 알아보도록 하겠다.

 

 

 

 

 

 

 

 

깊이 우선 탐색(DFS)는 탐색을 할 때 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘이다.

이러한 깊이 우선 탐색은 맹목적으로 각 노드를 탐색할 때 주로 사용된다.

이전에 배웠던 너비 우선 탐색에서는 큐를 사용하였고, 이번 깊이 우선 탐색에서는 스택을 사용한다.

컴퓨터는 항상 스택의 원리를 사용하기 때문에 사실 스택을 사용하지 않아도 된다.

 

 

 

 

 

 

 

맨 처음에 시작 노드(Start Node)를 스택에 넣어주고  시작 노드를 방문했음을 알리는 방문 표시를 한다.

그 다음에는 다음의 알고리즘을 반복한다.

 

1. 스택의 최상단 노드를 확인한다.

2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리한다.

   방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 뺀다.

 

 

 

 

 

 

 

 

 

이 깊이 우선 탐색을 stl vector를 사용해서 구현해보도록 하겠다.

 

#include <iostream>
#include <vector>
using namespace std;

int number = 7;
int c[8];
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() {
	// 1과 2를 연결한다.
	a[1].push_back(2);
	a[2].push_back(1);

	// 1과 3을 연결한다.
	a[1].push_back(3);
	a[3].push_back(1);

	// 2와 3을 연결한다.
	a[2].push_back(3);
	a[3].push_back(2);

	// 2과 4를 연결한다.
	a[2].push_back(4);
	a[4].push_back(2);

	// 2와 5를 연결한다.
	a[2].push_back(5);
	a[5].push_back(2);

	// 3과 6을 연결한다.
	a[3].push_back(6);
	a[6].push_back(3);

	// 3과 7을 연결한다.
	a[3].push_back(7);
	a[7].push_back(3);

	// 4와 5를 연결한다.
	a[4].push_back(5);
	a[5].push_back(4);

	// 6과 7을 연결한다.
	a[6].push_back(7);
	a[7].push_back(6);

	// BFS를 수행한다.
	DFS(1);

	return 0;
}

 

 

출력 결과는 1 2 3 6 7 4 5가 나온다.

 

 

 

이 방법은 스택을 사용하지 않고 재귀 함수를 이용해 구현했다.