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

해당 글은 공부를 하면서 적은 글이기 때문에 틀릴 수 있습니다. 참고용으로만 봐주세요~

1. 서론

깊이 우선 탐색 (DFS, Depth-First Search)은 그래프 자료구조에 기반한 대표적인 탐색 알고리즘 중 하나이다.

DFS를 활용하기 위해서는 우선적으로 큐(Queue), 스택(Stack), 그래프(Graph) 자료구조에 대한 이해가 선행되어야 한다.

 

큐와 스택에 대한 글은 따로 포스팅할 예정이다.

 

그래프 탐색이란

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다.

Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지

 

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

깊이 우선 탐색이란

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기의 노드를 완벽하게 탐색하는 방법이다.

즉, 해당 분기의 가장 깊은 노드까지 도달하였을 때 경로를 역추적하여 되돌아 나오는 탐색 방법이다.

이때 주의할 점은 이미 방문한 노드를 다시 방문하지 않기 위해 방문한 노드를 따로 저장해야 한다.

이를 '방문 처리'라고 한다.

 

방문처리를 하지 않을 경우 무한루프에 빠질 위험이 있기 때문에 반듯이 해주어야하는 작업이다.

 

깊이 우선 탐색(DFS)의 특징

• 자기 자신을 호출하는 순환 알고리즘 형태를 가지고 있다.
• 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.

 장점

• 현재 분기상의 노드들만 기억하면 되기 때문에 저장 공간의 수요가 비교적 적다.
• 목표 노드가 깊은 단계에 있을 경우 탐색을 빨리 마칠 수 있다.

단점

• 목표 노드가 없는 분기에 깊이 탐색할 가능성이 있다.
  즉, 목표 노드가 없어도 검사하는 분기마다 우선적으로 가장 깊은  노드를 탐색하기 때문에 상황에 따라 탐색 시간이 오래 걸릴 수 있다.
  때문에 지정한 임의의 깊이까지만 탐색을 하고 목표노드를 발견하지 못하면 다음 분기를 따라 탐색하는 방법이 더 유효할 수 있다.
• 목표 노드까지 도달했던 경로가 최단 경로라는 보장이 없다.
  때문에 단순 노드 탐색이 아닌 경로 탐색일 경우 최단 거리를 구하기에 적합하지 않다.
• 방문 처리를 하지 않을 경우 무한 루프에 빠질 위험이 있다.

 

DFS의 동작 순서

DFS의 동작 순서를 정리하면 다음과 같다.

1. 루트 노드에 방문하고, 방문처리 한다.
2. 루트 노드와 인접한 노드를 방문한다.
3. 방문한  노드가 인접한 노드를 방문한다.
    인접한 노드가 없을 경우 이전 노드로 이동해 다른 인접 노드를 방문한다.
4. 모든 노드가 순회될 때, 혹은 탐색하려는 목표 노드가 발견될 때 까지 2 ~ 3번을 반복한다.

그림을 보며 한번 확인해보자.

<조악하게.. 그린 이진 트리>

이렇게 각 노드가 연결된 이진트리가 있다고 가정을 하고, DFS의 순회 순서와 동작 방법을 살펴보자.

우리는 시작 노드를 Root Node인 A로 설정하고, 목표하는 노드는 K노드로 가정해 보자.

1. A노드를 방문해 목표로 하는 노드인지 확인하고, 맞다면, 탐색을 종료하고, 아니라면 방문 체크를 한 뒤 인접 노드(B)로 이동한다.
2. B가 목표하는 노드인지 확인한 뒤, 1번과 같은 분기처리로 방문처리를 한 뒤 D로 이동한다.
3. D는 목표 노드(K)가 아니기 때문에 방문처리를 한 뒤 인접 노드(H)로 이동한다.
4. H는 목표 노드(K)가 아니기 때문에 방문 처리를 한다. 인접 노드로 이동하려 보니, 인접 노드가 없기 때문에 D로 다시 올라간다.
5. D의 인접 노드 중 방문 처리가 되지 않은 노드가 없기 때문에 B로 이동한다.
6. B의 인접 노드 중 D는 방문 처리가 되어 있고, E는 방문 처리가 되어 있지 않기 때문에 E로 이동한다.
7. 이러한 방법으로 K노드까지 순회하며 탐색한다.

 이렇게 탐색을 마치고 나면 경로는 다음과 같다.

즉, A - B - D - H - E - I - J - C - F - G - K 순으로 순회를 하게 된다.

 

순회 순서를 확인해 보면 순회 순서가 최단 거리(A - C - G - K)는 아니다.

최단 거리를 알기 위해서는 최단 거리를 찾는 구조를 따로 설계하면 찾을 수 있으나 다른 알고리즘에 비해 최단 거리를 찾는 성능이 떨어지는 편이다. (따라서 최단 거리를 찾을 때는 A* 알고리즘 등을 이용하면 된다. 따지고 보면 이런 길 찾기 알고리즘도 BFS 등의 순회 알고리즘을 이용하기 때문에 DFS, BFS를 먼저 공부하고 길 찾기 알고리즘을 따로 찾아보면 좋을 것 같다.)

 

물론, 왼쪽을 먼저 탐색할지, 오른쪽 노드를 먼저 탐색할지는 코드에 따라 달라질 수 있다. 하지만 깊이 우선 탐색의 중점은 해당 분기의 가장 깊은 곳까지 탐색을 하고, 다시 분기가 나뉘는 노드로 돌아와 다른 분기의 가장 깊은 곳까지 탐색하는 것이다.

 

이진트리의 경우 순회 순서에 따라 전위 순회, 중위 순회, 후위 순회로 나뉜다.

해당 이진트리의 DFS 순회는 따로 포스팅할 것이다.

 

다른 예시로 그래프를 살펴보자.

<다시 한번 더 그림판으로 그린 그래프..>

다시 시작 노드를 A로 가정하고, 이번에는 목표 노드 없이 순회가 어떻게 이루어지는지만 확인해 보자.

위의 그래프를 깊이 우선 탐색으로 진행하면 A - B - E - F - G - C- D 순으로 순회하게 된다.

 

깊이 우선 탐색(DFS)의 구현

깊이 우선 탐색이 무엇이고, 어떻게 동작하는지를 확인했으니 한번 구현해 보자.

구현하는 방법 2가지를 살펴보자.

1.  재귀함수를 이용한 구현
2. 명시적인 스택을 사용한 구현

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

using namespace std;

int N, M, S;
vector<int> adjList[1001];
bool isVisited[1001] = { false, };
stack<int> st;

// 재귀함수를 이용한 dfs
void dfs(int V)
{
	// 이미 방문을 했다면 return 한다.
	if (isVisited[V])
		return;
	cout << V;

	for (int i = 0; i < adjList[V].size(); ++i)
	{
		// 인접 노드 가져오기
		int iNext = adjList[V][i];
		// 인접 노드 재귀함수 호출
		dfs(iNext);
	}
}

// stack을 이용한 dfs
void stackdfs(int V)
{
	// 루트 노드 삽입
	st.push(V);

	while (!st.empty())
	{
		int cur = st.top();
		st.pop();

		if (isVisited[cur])
			continue;

		cout << cur;

		isVisited[cur] = true;

		// 숫자가 작은 노드를 먼저 방문하기 위해 reverse
		for (int i = adjList[cur].size() - 1; i >= 0; --i)
		{
			int iNext = adjList[cur][i];
			st.push(iNext);
		}
	}
}

int main()
{
	int N, M, S;
	cin >> N >> M >> S;

	for (int i = 0; i < M; ++i)
	{
		int s, e;
		cin >> s >> e;
		adjList[s].push_back(e);
		adjList[e].push_back(s);
	}

	// 정렬
	for (int i = 0; i < 1001; ++i)
	{
		sort(adjList[i].begin(), adjList[i].end());
	}

	fill_n(isVisited, 1001, false); // 방문 여부 초기화
	stackdfs(S);

	return 0;
}

해당 코드는 https://sweetday-alice.tistory.com/176 블로그의 코드를 가져왔다.

추후에 직접 코드를 짜서 올릴 예정입니다.

위 블로그에 들어가 보면 Queue를 이용해 만든 dfs도 존재한다.

 

깊이 우선 탐색(DFS)의 시간 복잡도

• DFS는 그래프(정점의 수: N, 간선의 수: E)의 모든 간선을 조회한다.
  • 인접 리스트로 표현된 그래프: O(N+E)
  •  인접 행렬로 표현된 그래프: O(N^2)
• 즉, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

 

참고 블로그 및 자료

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

 

[C++] DFS와 BFS 구현하기