깊이 우선 탐색(Depth First Search, DFS) 알고리즘

이번에는 깊이 우선 탐색에 대해 알아보자.

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

깊이 우선 탐색(depth-first search: DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.
출처 : 위키백과

깊이 우선 탐색(Depth First Search)은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 탐색하는 알고리즘이다. 이러한 깊이 우선 탐색은 맹목적으로 각 노드를 탐색할 때 주로 사용된다. 너비 우선 탐색(Breadth First Search) 에서는 큐(Queue)가 사용되었다면 깊이 우선 탐색(Depth First Search) 에서는 스택(Stack)이 사용된다. 더하여 사실 스택을 사용하지 않아도 구현이 가능하다는 특징이 있다. 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문이다.

특징

자기 자신을 호출하는 순환 알고리즘의 형태를 가진다.
그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.

다음의 그림을 보자

DFS는 맨 처음에 시작 노드(Start Node)를 스택에 삽입하면서 시작한다. 또한 시작 노드를 방문했다고 방문 처리 를 해주도록 한다.

이제 DFS는 다음과 같은 알고리즘에 의해 동작한다.

스택의 최상단 노드를 확인한다.
최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 뺀다.

위의 1번과 2번을 계속해서 반복하면 된다.

스택에 있던 최상단 노드가 1번 노드이므로 인접한 노드 중 방문하지 않은 2번 노드를 삽입한다.

이후에 2번 노드의 인접 노드 중 방문하지 않은 노드인 3번 노드를 스택에 삽입한다.

이어서 3번 노드의 인접 노드 중 방문하지 않은 6번 노드를 스택에 삽입

6번 노드의 인접 노드 중 방문하지 않은 7번 노드를 삽입

7번 노드, 6번 노드, 3번 노드는 인접 노드를 모두 방문하였기 때문에 스택에서 빠져나오게 된다. 이후에 2번 노드를 보았을 때 인접 노드인 4번 노드를 아직 방문하지 않았으므로 스택에 넣는다.

결과적으로 4번 노드의 인접 노드인 5번 노드가 스택에 들어가고 이후에 스택에서 하나씩 다 노드들이 빠져나오게 된다. 결과적으로 다음 그림과 같다.

따라서 방문 경로는 1 - 2 - 3 - 6 - 7 - 4 - 5 이다.

#include<iostream>
#include<vector>

using namespace std;

int const number = 7;
int c[8]; // 방문한 노드인지 기록
vector<int> a[8]; // 그래프를 표현할 벡터

void dfs(int x)
{
	if (c[x]) return; // 방문했던 노드면 리턴
	c[x] = true; // 방문 처리
	cout << x << ' ';
	for (int i = 0; i < a[x].size(); i++) // 각 벡터에 연결된 노드 수만큼 반복
	{
		int y = a[x][i]; // 현재 노드
		dfs(y); // 재귀 함수로 스택을 구현
	}
}

int main(void)
{
	// 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);
	// 3과 6을 연결
	a[3].push_back(6);
	a[6].push_back(3);
	// 3과 7을 연결
	a[3].push_back(7);
	a[7].push_back(3);
	// 4와 5를 연결
	a[4].push_back(5);
	a[5].push_back(4);
	// 6과 7을 연결
	a[6].push_back(7);
	a[7].push_back(6);
	// BFS 수행
	dfs(1);
}

결과는 위와 같이 1 - 2 - 3 - 6 - 7 - 4 - 5 의 순서로 탐색이 된 것을 확인할 수 있다.

참조
https://blog.naver.com/ndb796/221230945092
https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

Algorithm

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

특징

FEATURED TAGS

FRIENDS