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

● 1. 깊이 우선 탐색의 개념

● 2. 깊이 우선 탐색의 특징

● 3. 깊이 우선 탐색의 구현

그래프 탐색이란

그래프 안에 어떤 버텍스들이 있는지 알고 싶을 때 사용한다.

DFS는 버텍스의 자식들을 먼저 탐색하고, BFS는 버텍스의 형제들을 먼저 탐색한다.

ex) 미로 탈출, 최단거리 탐색, 특정 지점에서 다른 점으로 갈 수 있는지 등의 문제를 해결할때 사용하는 알고리즘

 

1. 깊이 우선 탐색의 개념 

 

[그림1 : 깊이 우선 탐색, 출처 : 위키백과]

 

 

깊이우선 탐색 (Depth First Search) : 탐색 트리의 특정 노드를 방문하여 확인한 후 그 노드와 연결된 자식노드 중에서 우선 순위가 가장 빠른 하나를 선택해 방문하며 그후 더 이상 방문할 곳이 없으면 이전 상태로 되돌아가는 탐색 방법이다.

이때 탐색 과정이 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)을 사용한다. 깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 부모노드로 되돌아(백트레킹, backtracking)와서, 부모노드에서 이전과는 다른 자식노드를 선택하여 방문한다. 

 

깊이우선 탐색은 재귀함수의 호출/실행 과정과 완전히 똑같다.

넓게 탐색하기 전에 깊게 탐색한다.

모든 노드를 방문(브루트 포스, Brute Force)하고자 하는경우 사용한다. 

DFS가 BFS보다 간단하지만 단순 검색 속도 자체는 BFS가 더 빠르다.

 

 

2. 깊이 우선 탐색의 특징

재귀함수 또는 스택구조를 사용하여 LIFO구조 이다. 

그래프 탐색구현시 어떤 정점을 방문했는지 여부를 처리해야한다. 

전위순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.

전위순회(Pre-Order)

1. root를 방문한다.

2. 왼쪽 subtree를 방문한다.

3. 오른쪽 subtree를 방문한다.

특징 : 루트가 가장먼저 나온다

[그림2 : 전위순회 트리 방문 순서]

이외에도 중위순회(In-order Traversal), 후위순회(Post-order Traversal), 레벨순회(Level-order Traversal)가 있다.

 

3. 깊이 우선 탐색의 구현

스택(stack)구조나 재귀(recursion) 함수를 이용

재귀함수 사용

/*************재귀 호출을 이용한 DFS 코드*******************/
void DFS(int k){ //k번째 정점에 대해 탐색
	visited[k] = true; //방문 체크
	for(int i = 1; i <= n; i++){
		if(G[k][i] && !visited[i]){ //이웃 정점에 대해 방문하지 않은 노드 탐색
		DFS(i); //마지막으로 탐색한 노드부터 다시 탐색
		}
	}
	return; //k정점의 모든 인접 정점을 방문한 경우, 백트랙
}

 

스택구조 사용

/*************스택 구조를 이용한 DFS 코드*******************/
void DFS(int k){

	stackClass<int> DFS;
	DFS.pust(root); // 시작점 push
	visited[root] = 1;

	while(!DFS.isEmpty() && k != stack.GetTop()){
		if(All Adjacent Cities Are Visited){   // 인접 노드를 모두 방문한 경우
			stack.pop();
		}
		else{
			//인접 노드 중 하나를 선택
			stack.push(New);
			visited[New] = 1;
		}
	}
	if(stack.isEmpty()) cout<<"NO";
	else cout<<"YES"; 
}

 

필자는 알고리즘 문제 중 DFS를 활용하는 문제들을 풀때 아래와 같은 기초 바탕 코드를 사용한다. 

항상 배열을 활용하며 3구조를 나눠져 있다.

void dfs() {
	if(모든 조건 충족) {				//1
		결과 계산
	} else { 
	dfs()						//2
}

void dfs() {
	if(모든 조건 충족) {				//1
		결과 계산
	} else {
	arr[] = 					//2
	dfs()						//3
	arr[]==
}

void dfs() {
	if(모든 조건 충족) {				//1
		결과 계산
	} else {
	for() {	
		arr[] =					//2 
		dfs()					//3
		arr[]==
	}
}

 

관련 문제

 

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

https://www.acmicpc.net/problem/1743

1743번: 음식물 피하기

https://www.acmicpc.net/problem/10451

10451번: 순열 사이클

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

 

 

내 제출 코드 : 

http://boj.kr/61c560eb47b44c5ab40266257119b1fd

http://boj.kr/e5344b144b404c06b5038ad8a1b91dc8

http://boj.kr/ed17e0e5648d449db79cd49c75696aaf

http://boj.kr/4d842fcbc0fd4a59bc62d3cb6100ecdd

http://boj.kr/4101d94fc879445ea43e0af34d372385

http://boj.kr/4a0b62d59e774fae9ddb99ec876a661d