탐색 알고리즘 - 깊이 우선 탐색(Depth First Search, DFS)

깊이 우선 탐색(Depth First Search, DFS)

 

깊이 우선 탐색이란?

 

 - 임의의 노드에서 다음 분기로 넘어가기 전 해당 분기를 모두 탐색하는 것.

 

 - 순환 알고리즘의 형태

 

 - 그래프 탐색 시 방문 노드를 반드시 검사해야 한다.

 

 - 스택 또는 재귀를 이용하여 구현한다.

 

---

 

깊이 우선 탐색 방법

 

 - 1. A노드를 방문하고, 방문한 노드를 표시한다.

 

 - 2. A노드와 인접한 B노드를 방문하고, 방문한 노드를 표시한다.

 

 - 3. B노드와 인접한 C노드를 방문하고, 방문한 노드를 표시한다.

 

 - 4. C노드와 인접한 노드가 없는 경우, 다시 B노드로 돌아가서 다른 인접한 노드가 있는지 탐색한다.

 

 - 5. 위 과정을 반복하여 모든 노드를 탐색한다.

 

 

 

1. 노드 0 ~ 5인 그래프가 주어졌다.

 

2. 노드 0을 탐색한 후 인접한 노드 1를 탐색한다.

3. 노드 1을 탐색한 후 인접한 노드 중 하나인 2를 탐색한다.

4. 노드 2을 탐색한 후 인접한 노드 중 하나인 3을 탐색한다.

 

 

5. 노드 3을 탐색한 후 노드 3의 인접한 노드 중 탐색하지 않은 노드가가 없기 때문에 이전 노드인 노드 2로 돌아간다.

 

6. 노드2로 돌아간 후 노드 4를 탐색한다.

 

 

5. 노드 4를 탐색한 후 인접한 노드 중 가장 작은 노드인 5를 탐색한다.

6. 모든 노드 탐색이 완료되었다.

 

---

 

깊이 우선 탐색 코드(C++)

 

 - 1. 재귀 이용

#include <iostream>
#include <vector>

using namespace std;

bool visit[6];

// 재귀 이용
void DFSRecursive(vector<vector<int>> &v, int node)
{

	visit[node] = true;
	cout << "노드 " << node << " 방문 " << endl;
	for (auto index : v[node])
	{
		if (!visit[index]) {
			DFSRecursive(v, index);
		}
			
	}
}


int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	
	vector<vector<int>> v{ {1},{0,2,5},{1,3,4},{2},{2,5},{1,4} };
	DFSRecursive(v, 0);
	return 0;
}

 

실행 결과

 

 

 - 2. 스택 이용

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

bool visit[6];

// 스택 이용
void DFSStack(vector<vector<int>> &v, int node)
{

	stack<int> s;
	s.push(node);
	visit[node]=true;
	int nowNode=node;

	while (!s.empty())
	{
		nowNode = s.top();
		s.pop();
		cout << "노드 " << nowNode << " 방문 " << endl;
		for (auto index : v[nowNode])
		{
			if (!visit[index])
			{
				s.push(index);
				visit[index] = true;
			}
		}
	}

}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	
	vector<vector<int>> v{ {1},{0,2,5},{1,3,4},{2},{2,5},{1,4} };
	DFSStack(v, 0);
	return 0;
}

 

 

실행 결과