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

깊이 우선 탐색(DFS) 이란?

깊이 우선 탐색 (DFS, Depth First Search)은 BFS와 함께 대표적인 그래프 탐색 방법 중 하나입니다.

일반적으로 DFS 알고리즘을 구현할 때 스택을 이용하고, 유사하게 재귀함수를 이용하여 구현하기도 합니다.

DFS 알고리즘은 스택을 이용해서 갈 수 있는만큼 최대한 이동을 하며, 만약 갈 수 없다면 이전 정점으로 돌아갑니다.

깊이 우선 탐색(DFS) 방법

아래는 DFS를 설명하기 위해 작성한 간단한 그래프입니다.

여기서 원으로 둘라싸인 1, 2, 3 .. 등은 정점(Vertex)라 하고, 정점과 정점을 잇는 선을 간선(Edge)이라고 합니다.

우선 시작점을 1로 정하고 DFS 알고리즘을 바탕으로 탐색을 진행해 보겠습니다.

 

출발점인 1을 스택에 입력하고, 방문표시를 합니다.

 

정점 1과 연결된 정점 중 2를 선택하여 이동을 하고, 정점 2를 스택에 입력하며, 정점 2도 방문 표시를 합니다.

 

 

정점 2와 연결된 정점 중 4를 선택하여 이동을 하고, 정점 4를 스택에 입력하며, 정점 4도 방문 표시를 합니다.

 

정점 4에서 연결 가능한 정점 중 방문하지 않은 7로 이동합니다. 이후 스택에 7을 입력하고, 정점 7을 방문표시 합니다.

 

정점 7에서 연결가능한 정점 중 방문하지 않은 5로 이동합니다. 이후 스택에 5를 입력하고, 정점 5를 방문표시 합니다.

 

정점 5와 연결된 정점 중에서 방문하지 않은 정점이 없기 때문에 이전에 위치한 정점 7로 이동합니다.

이를 표현하기 위해 스택에서 5를 제거합니다.

 

 

정점 7과 연결된 정점 중에서 방문하지 않은 정점 6으로 이동합니다.

이후 스택에 6을 입력하고, 정점 6을 방문표시 합니다.

 

정점 6에서 이동가능한 정점이 3으로 이동합니다. 이후 스택에 3을 입력하고, 정점 3을 방문표시 합니다.

정점 3까지 방문하면 모든 정점을 다 방문한 것을 확인 할 수 있습니다.

 

깊이 우선 탐색(DFS) 예제

백준 1260번: DFS와 BFS

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

int n, m; // 정점, 간선
int v; // 탐색을 시작할 정점의 번호
int s, e; //시작점, 끝점
int matrix[1002][1002];
int visit[1002];
queue<int> Q;
int check[1002];

void dfs(int x)
{
	visit[x] = 1;
	printf("%d ", x);
	for (int i = 1; i <= n; i++)
	{
		if (matrix[x][i] == 1 && visit[i] == 0)
			dfs(i);
	}
}

void bfs(int x)
{
	check[x] = 1;
	Q.push(x);
	while (!Q.empty())
	{
		int t = Q.front();
		Q.pop();
		printf("%d ", t);
		for (int i = 1; i <= n; i++)
		{
			if (matrix[t][i] == 1 && check[i] == 0)
			{
				check[i] = 1;
				Q.push(i);
			}
		}
	}
}


int main(int argc, char *argv[])
{
	scanf("%d %d %d", &n, &m, &v);
	for (int i = 0; i < m; i++)
	{
		scanf("%d %d", &s, &e);
		matrix[s][e] = matrix[e][s] = 1;
	}
	dfs(v);
	printf("\n");
	bfs(v);
	printf("\n");

	return 0;
}