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

깊이 우선 탐색?

그래프에서 깊은 부분(자식들)을 우선적으로 탐색하는 방식이다. DFS는 스택이나 재귀 함수를 사용해서 구현할 수 있다. 탐색 과정이 한없이 진행되는 것을 막고 싶다면 깊이 제한(depth bound)를 사용해서 한업이 진행되는 탐색을 막을 수 있다.

장점

현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적음
최선의 경우, 가장 빠른 알고리즘. 운 좋게 항상 해에 도달하는 올바른 경로를 선택한다면, 깊이 우선 탐색이 최소 실행시간에 해를 찾음
찾으려는 노드가 깊은 단계에 있다면 BFS보다 빠르게 찾을 수 있음

단점

찾은 해가 최단 경로가 된다는 보장이 없음
최악의 경우, 가능한 모든 경로를 탐험하고서야 해를 찾으므로, 해에 도달하는 데 가장 오랜 시간이 걸림

 

구현

스택

fun dfs(n: Int, array: Array<IntArray>, start: Int) {
    val visited = BooleanArray(n) { false }
    val stack = Stack<Integer>()
    stack.push(start)
     while (!stack.isEmpty()){
        int v = stack.pop()
        if (!visited[v]){
            visited[v] = true
            for (i in 0 until array[v].size) {
            	val dest: Int = array[v].get(i)
                if (!visited[dest]) stack.push(dest)
            }
        }
    }
}

fun main() {
	val array = intArrayOf([0,1],[0,2],[1,2])
	dfs(3, array, 0)
}

 

재귀함수

fun dfs(visited: BooleanArray, array: Array<IntArray>, start: Int) {
    visited[start] = true
    for (i in array[start].indices) {
        if(array[start][i] == 1 && !visited[i]) {
            dfs(visited, array, i)
        }
    }
}

fun main(n: Int, array: Array<IntArray>) {
    val visited = BooleanArray(n) { false }
    for (i in array.indices) {
       if(!visited[i]) {
            dfs(visited, array, i)
       }
    }
}

 

 

보통 DFS는 아래와 같은 문제 유형에서 주로 사용이 됩니다.

• 그래프의 모든 정점을 방문하는 문제
• 경로들을 특징해서 저장해야 하는 문제
• 검색 대상의 그래프가 많이 큰 경우
• 사이클이 존재하는 경로를 찾는 경우