[C/C++] 깊이 우선 탐색(DFS)

깊이 우선 탐색이란?

깊이 우선 탐색(depth-first search, DFS)은 맹목적 탐색방법의 하나로 깊이를 우선적으로 탐색하는 방법이다.

 

깊이 우선 탐색은 스택과 관련 있습니다.

 

 

 

 

이진 트리

 

예를 들어 위와 같은 이진트리가 있습니다.

가장 먼저 루트 노드를 방문합니다. DFS와 마찬가지로 방문하면 방문 체크를 해줍니다.

스택 1

방문체크 1

 

스택의 최상단 노드와 연결된 노드 중 하나를 방문합니다. 2번 노드를 방문합니다.

스택 1-2

방문체크 1-2

 

아직 방문하지 않은 노드가 있으면 방문합니다. 3번 노드를 방문합니다.

스택 1-2-3

방문체크 1-2-3

 

최상단 노드와 연결된 방문하지 않은 노드가 없다면 꺼냅니다. 3번 노드와 연결된 노드 중 방문하지 않은 노드가 없으므로 꺼냅니다.

스택 1-2

방문체크 1-2-3

 

최상단 노드는 2번인데 방문하지 않은 노드가 있으므로 방문합니다. 4번 노드를 방문합니다.

스택 1-2-4

방문체크 1-2-3-4

 

최상단 노드와 연결된 방문하지 않은 노드가 없다면 꺼냅니다. 최상단 4번 노드와 연결된 노드중 방문하지 않은 노드가 없으므로 꺼냅니다.

스택 1-2

방문체크 1-2-3-4

 

최상단 노드는 2번인데 방문하지 않은 노드가 있으므로 방문합니다. 5번 노드를 방문합니다.

스택 1-2-5

방문체크 1-2-3-4-5

 

DFS의 동작 핵심은 다음과 같습니다.

 

1. 루트 노드 방문 후 방문 체크

2. 최상단 노드와 연결된 1개의 노드를 방문 후 방문 체크

3. 최상단 노드와 연결된 방문하지 않은 노드가 없다면 꺼낸다.

4. 2, 3번을 반복한다.

 

#include <stdio.h>
#include <vector>

using namespace std;

int check[6];	//방문체크
vector<int> a[5];

void dfs(int top){
	if(check[top]==true) return;	//방문 했다면 그냥 리턴 
	check[top] = true;	//방문체크
	printf("%d ", top);	//방문했다고 표시(출력)
	
	//최상단 노드와 연결된 노드 방문시도
	for(int i=0;i<a[top].size();++i){
		dfs(a[top][i]);	//연결된 노드 방문시도, 스택 쌓기
	}
}

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);
	
	dfs(1);	//루트 노드 방문
	
	return 0;
}

 

결과값:

1 2 3 4 5

 

함수 호출은 컴퓨터 시스템 내부상 스택으로 쌓기게 됩니다. 스택을 구현하지 않더라도 재귀 함수 호출로 구현할 수 있습니다.

 

지금 까지 깊이 우선 탐색의 동작 원리에 대해 알아봤습니다. DFS는 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적으나 얻어진 해가 최단 경로가 된다는 보장이 없습니다.