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

깊이 우선 탐색 : 탐색을 할 때 깊이를 우선으로 하여 탐색을 수행하는 탐색 알고리즘

​

' 맹목적으로 각 노드를 탐색 ' 할 경우 주로 사용하는 탐색 기법으로, 모든 노드를 방문하고자 하는 경우 ( 완전 탐색) 사용

너비 우선 탐색 ( BFS) 보다 지나온 경로를 쉽게 파악할 수 있다는 장점이 있다.

또 층별로 모든 자식 노드를 저장해야 할 필요가 없기 때문에 BFS에 비해 메모리 요구량이 훨씬 적다

​

※ 어느 방향으로 검색할지 확률에 따라 속도가 많이 빨라질 수도 있고 느려질 수도 있다.(확률 의존)

​

깊이 우선 탐색을 수행하기 위해서 필요한 준비물은 Stack이다. 이다.

※컴퓨터는 구조적으로 스택의 원리를 사용하기 때문에 재귀 함수를 사용하여 구현이 가능하다.

​

이제 어떤 식으로 정렬이 이루어지는지 보자면!

다음과 같이 1 2 3 4 5 가 서로 연결되어 있다고 보았을 때 깊이 우선 탐색을 해보자면

​

시작 노드 ( Start Node )를 스택에 삽입해 주고 시작한 노드는 방문했다는 뜻으로 ' 방문처리 '를 해줍니다.

방문처리는 주황색으로 하였습니다.

​

그 후 인접 노드 2를 스택에 넣어주고 방문처리를 해주었습니다.

2의 인접노드 3을 스택에 넣어주고 방문처리를 해줍니다!

3의 인접노드 5를 스택에 넣어주고 방문처리를 해줍니다.

이후 5의 인접 노드가 너 없기 때문에 스택에서 내보냅니다.

3의 인접 노드도 전부 방문했기 때문에 스택에서 내보냅니다.

2의 인접 노드 중 방문하지 않은 4를 스택에 넣어줍니다.

이렇게 모든 탐색이 종료되고 깊이 우선 탐색의 탐색 순서는 1 2 3 5 4 순으로 탐색이 이루어졌습니다.

​

이제 깊이 우선 탐색을 C++ 코드로 나타내 보자면!

#include <iostream>   // C++ 헤더
#include <vector>

int number = 5;
int c[5];
vector<int> a[5];

void dfs(int start) {

	if (c[start]) return;
	c[start] = true;

	cout << start+1 << ' ';

	for(int i = 0; i < a[start].size(); i++){
		int y = a[start][i];
		dfs(y);
	}
}


int main(void) {
	a[0].push_back(1);
	a[1].push_back(0);

	a[0].push_back(2);
	a[2].push_back(0);

	a[2].push_back(1);
	a[1].push_back(2);

	a[1].push_back(3);
	a[3].push_back(1);

	a[2].push_back(4);
	a[4].push_back(2);

	dfs(0);
}

자바로 코딩해보자면!

 

import java.util.LinkedList;

public class Strudy_DFS {

	public static LinkedList<LinkedList<Integer>> list = new LinkedList<>();
	public static boolean [] arr = new boolean[5];
	
	public static void main(String[] args) {
		
		for(int i = 0; i < 5; i++)
			list.add(new LinkedList<Integer>());
		
		list.get(0).add(2);
		list.get(1).add(1);
		
		list.get(0).add(3);
		list.get(2).add(1);
		
		list.get(1).add(3);
		list.get(2).add(2);
		
		
		list.get(1).add(4);
		list.get(3).add(2);
		
		list.get(2).add(5);
		list.get(4).add(3);
		DFS(1);
	}
	
	static void DFS(int start) {
		
		int st = start -1;
		
		if(arr[st]) return;
		
		arr[st] = true;
		
		System.out.println(start);
		
		for(int i = 0; i < list.get(st).size(); i++)
			
			DFS(list.get(st).get(i));

	}
}

DFS 또한 BFS처럼 DFS 자체로는 큰 의미가 없고 깊이를 우선으로 적용하여 탐색한다는 특성이

중요한 것이고, DFS를 이용하여 문제를 해결하고자 하는 것과 다른 알고리즘에 사용되는 점이 중요점입니다.

또한 스택을 직접 사용하지 않고 재귀 함수를 이용하여 작성한 것이 프로그래밍 대회에서 더 자주 활용된다는 점을 알아두자!