[알고리즘] DFS (깊이 우선 탐색)

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

1. 완전 탐색 알고리즘
 - 모든 경우의 수를 탐색하는 알고리즘

2. 한 루트로 최대한 깊이 탐색하는 방식
 - 트리나 그래프에서 한 루트로 쭉 탐색하다가 끝에 도달하면 다시 이전으로 돌아와서 다른 루트로 가는 방식
 - 미로 찾기에서 한 방향으로 쭉 가다가 막히면, 다시 이전 분기점으로 돌아와서 다른 방향으로 가보면서 모든 루트를 탐색하는 방식

출처 : 위키백과 https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89#/media/%ED%8C%8C%EC%9D%BC:Depth-First-Search.gif

 

2. 장점

1) 저장 공간의 수요가 비교적 적다.
 - 현 경로상의 노드들만 기억하면 되므로
2) 목표 노드가 깊은 단계에 있을 경우, 해를 빨리 구할 수 있다.

 

3. 단점

1) 해가 없는 경로에 깊이 빠질 가능성이 있다.
 - 미리 지정한 임의의 깊이까지만 탐색하고 목표 노드를 발견하지 못했다면, 다른 경로를 따라 탐색하는 방식이 유용할 수 있다.
2) 얻어진 해가 최단 경로가 된다는 보장이 없다.
 - 경로가 다수인 경우, 탐색한 거리가 최단 거리라고 보기는 힘들다.

 

4. 구현

 1) 재귀 방식

• 주로 사용하는 방식

#include <iostream>
#include <vector>

using namespace std;

bool visited[11];
vector<int> graph[11];

void dfs(int current_node)
{
	visited[current_node] = true;	// 방문 여부 체크
	cout << current_node << " ";	// 현재 노드 출력

	for (int index = 0; index < graph[current_node].size(); index++)
	{
		int next_node = graph[current_node][index];
		if (visited[next_node]) continue;	// 방문한 노드라면 넘어가기
		dfs(next_node);	// 다음 노드 탐색
	}
}

int main() {
	// graph 생성
	graph[1].push_back(2);
	graph[1].push_back(5);
	graph[1].push_back(9);

	graph[2].push_back(3);

	graph[3].push_back(4);

	graph[5].push_back(6);
	graph[5].push_back(8);

	graph[6].push_back(7);

	graph[9].push_back(10);

	// DFS (깊이 우선 탐색) 알고리즘
	dfs(1);

	return 0;
}

 

 2) Stack 방식

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

using namespace std;

bool visited[11];
vector<int> graph[11];

void dfs(int start_node)
{
	stack<int> s;
	s.push(start_node);
	visited[start_node] = true;
	cout << start_node << " ";

	while(!s.empty())
	{
		int current_node = s.top();
		s.pop();

		for (int index = 0; index < graph[current_node].size(); index++) {
			int next_node = graph[current_node][index];

			if (visited[next_node]) continue;

			cout << next_node << " ";
			visited[next_node] = true;

			s.push(current_node);
			s.push(next_node);
			break;
		}
	}
}

int main() {
	// graph 생성
	graph[1].push_back(2);
	graph[1].push_back(5);
	graph[1].push_back(9);

	graph[2].push_back(3);

	graph[3].push_back(4);

	graph[5].push_back(6);
	graph[5].push_back(8);

	graph[6].push_back(7);

	graph[9].push_back(10);

	// DFS (깊이 우선 탐색) 알고리즘
	dfs(1);

	return 0;
}

 

5. 알고리즘 구조

아래 3가지 순서로 나눌 수 있다.

1) 방문 여부 체크
2) 기저 조건
3) 다음 노드 탐색

void dfs(int current_node)
{
	// 1. 방문 여부 체크
	visited[current_node] = true;	// 방문 여부 체크

	// 2. 기저 조건
	if (current_node == 7) {
		cout << "7번 문 탈출!!";
		return;
	}

	// 3. 다음 노드 탐색
	for (int index = 0; index < graph[current_node].size(); index++)
	{
		int next_node = graph[current_node][index];
		if (visited[next_node]) continue;	// 방문한 노드라면 넘어가기
		dfs(next_node);	// 다음 노드 탐색
	}
}

 

 

6. DFS 문제 모음집

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

16724번: 피리 부는 사나이

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

9466번: 텀 프로젝트

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

2239번: 스도쿠

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

1987번: 알파벳

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

21736번: 헌내기는 친구가 필요해

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

14502번: 연구소

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

14888번: 연산자 끼워넣기

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