코딩 테스트를 볼 때 자주 등장하는 탐색 기법인 DFS (깊이 우선 탐색) 과 BFS (너비 우선 탐색) 에 대해 설명해보려고 한다.

이것들은 모두 그래프, 트리를 탐색하는 기법으로 중요성이 남다르니 제대로 한 번 알아야 한다.

언젠가 한 번 이에 대한 게시글도 써보려고 했는데, 백준에서 문제를 하나하나 풀다보니 DFS, BFS 문제들도 나오게 되어 이에 대해 글을 써본다.

DFS 란?

• 깊이 우선 탐색이라고도 불리며 Depth First Search 의 약자이다. 특정 노드부터 시작하여 가장 깊은 노드까지 탐색한 뒤, 다시 돌아온 후 다른 경로를 재탐색한다.
• 후입선출(LIFO) 원리를 가지며 대표적인 자료 구조는 Stack 이다.
• 가장 나중에 추가된 것을 가장 먼저 탐색한다.

DFS 의 동작 방식으로는 다음과 같다.

1. 새로운 길을 찾은 경우, 그것을 스택에 쌓는다. (최상위)
2. 다음 탐색은 스택의 최상위에 존재하는 것을 우선적으로 탐색한다.

쉽게 생각하면 한 경로를 끝까지 파다가 막다른 길이 나오면 되돌아와 다른 길을 파내는 것이다.

코드로 나타내보자 !

이제 위에서 설명한 DFS 를 코드로 나타내고 실행해보자.
다음 코드는 arr[1] 부터 시작하여 내부를 탐색하는 코드인데, 두 가지 방법으로 이를 나타낼 것이다.
우선 재귀 방식이다.

val arr = arrayOf(
    intArrayOf(),
    intArrayOf(3, 4),
    intArrayOf(),
    intArrayOf(5, 6),
    intArrayOf(7, 8),
    intArrayOf(),
    intArrayOf(),
    intArrayOf(),
    intArrayOf(),
)
var visitedArr = BooleanArray(arr.size)

fun dfsTest(){
    visitedArr[1] = true
    dfs(1)
    println("종료됨")
}

fun dfs(from: Int = 1){
    println("현재 진행 노드 - $from")

    for(to in arr[from]){
        if(!visitedArr[to]){
            visitedArr[to] = true
            println("방문 노드 - $to")
            dfs(to)
        }
    }
}

실행 결과 1 -> 3 -> 5(return) -> 6(return) -> 4 -> 7(return) -> 8(return) -> 종료 순으로 진행되는 것을 확인할 수 있다.

위에서 설명한 것 처럼 한 우물만 파다가 막히면 되돌아가는 특징을 확인할 수 있다 !

• 스택 방식

이번에는 스택 방식이다.
재귀 방식으로 사용하는 경우 매우 많은 재귀가 이루어지게 되는 경우, 함수 호출에 사용되는 Stack Memory 가 회수될 수 없어 StackOverflowError 가 발생할 수 있다.

그렇기에 DFS 를 이용할 때 재귀 방식이 아닌, 자료구조 스택 을 사용하여StackOverflowError 를 방지해줄 수 있다.
아래 예시에서는 스택이 아닌 ArrayDeque 를 사용하여 스택 방식을 구현하였다.

단, 이 방식은 재귀 방식에 비해 간결하지 않고 구현이 까다롭다는 단점이 있으므로 잘 선택해서 사용하자 .

val arr = arrayOf(
    intArrayOf(),
    intArrayOf(3, 4),
    intArrayOf(),
    intArrayOf(5, 6),
    intArrayOf(7, 8),
    intArrayOf(),
    intArrayOf(),
    intArrayOf(),
    intArrayOf(),
)
var visitedArr = BooleanArray(arr.size)

fun dfsTest(){
    dfs()
    println("종료됨")
}

fun dfs(start: Int = 1){
    val arrayDeque = ArrayDeque<Int>()

    // 후입 선출이므로 addLast
    arrayDeque.addLast(start)
    visitedArr[start] = true

    while (arrayDeque.isNotEmpty()){
        // 후입선출. 깊이 우선 탐색을 진행하기 위해 나중에 추가된 것을 먼저 진행하게 removeLast() 로 설정한다.
        val from = arrayDeque.removeLast()

        for(to in arr[from].reversed()){
            /*
            * 추가와 동시에 방문 기록에 추가하여 스택 쌓이지 않게 함. (무한 루프 방지)
            * 중복 노드가 들어갈 수 있으므로 add 때 visited 처리한다.
            * */
            if (!visitedArr[to]) {
                visitedArr[to] = true
                arrayDeque.addLast(to)
            }
        }

        println("현재 진행 노드 - $from : 현재 스택 = ${arrayDeque}")
    }
}

BFS 란?

• 너비 우선 탐색이라고도 불리며 breadth First Search 의 약자이다. 루트 노드에서 부터 시작하여 가까운 순서대로 탐색을 진행한다.
• 선입선출 (FIFO) 의 특징을 가진다
• 대표적인 자료구조로는 큐 (Queue) 가 존재한다.

LinkedList 로 구현이 가능하지만, ArrayDeque 로 구현하는 것이 성능상에서 이점이 존재하여 이를 통해 구현하겠다.

val arr = arrayOf(
    intArrayOf(),
    intArrayOf(3, 4),
    intArrayOf(),
    intArrayOf(5, 6),
    intArrayOf(7, 8),
    intArrayOf(),
    intArrayOf(),
    intArrayOf(),
    intArrayOf(),
)
var visitedArr = BooleanArray(arr.size)

fun bfs(start: Int = 1){
    val arrayDeque = ArrayDeque<Int>()

    arrayDeque.add(start)
    visitedArr[start] = true

    while (arrayDeque.isNotEmpty()){
        // 너비 우선 탐색을 진행하기 위해 먼저 추가된 것을 먼저 제거한다.
        val from = arrayDeque.removeFirst()

        for(to in arr[from]){
            /*
            * 추가와 동시에 방문 기록에 추가하여 스택 쌓이지 않게 함. (무한 루프 방지)
            * 중복 노드가 들어갈 수 있으므로 remove 가 아닌 add 때 visited 처리한다. 
            * */
            if(!visitedArr[to]){
                arrayDeque.add(to)
                visitedArr[to] = true
            }
        }

        println("현재 노드 : $from : 현재 큐 - ${arrayDeque}")
    }
}

🤘 DFS, BFS 에서 visited 처리를 하는 타이밍

내가 작성한 코드들을 살펴보면 dfs, bfs 에서 모두 visited 처리 및 건너뛰기를 add 하는 때에 사용하는 것을 알 수 있다.

이렇게 처리한 이유는 성능상 이점이 존재하기 때문인데, 그렇다면 remove 혹은 함수 호출때가 아닌, add 일 때 진행하게 된 이유가 무엇일까?

위와 같은 그래프가 있다고 생각해보자.

DFS 를 활용한다면 0 -> 1 -> 4,5,6,7,9,8,2 -> 3 순서로 진행.
BFS 를 활용한다면 0 -> 1 -> 2 -> 4,5,6,7,8,9 순서로 진행될 것이다.

이 때, remove. 즉, 다음 노드를 방문하는 차례에 아래와 같은 코드가 존재한다고 생각해보자.

fun visit(node: Int){
	if(visited) return
    visited[node] = true
}

1번 노드에 진입하여서 모든 자식 노드를 한번씩 진입하였음에도, 3번 노드를 진행하는 경우 2번 노드에 방문하는 함수를 또 호출할 수 있다.

현재는 2번 노드의 Degree (차수) 가 2이기에 추가 호출되는 것이 1번 뿐이지만, 차수가 100이라면 추가 호출이 99번이 진행되므로 매우 불필요한 작업이 아닐 수 없다.

이러한 작업으로 인해 시간 복잡도가 O(N) 에서 O(N + M) 까지 늘어날 수 있기에 visited 처리를 add 할 때 사용한 것이다.

참고

방문 기록, 순서 기록 등에 따라 visited 처리를 해야하는 위치가 달라질 수 있으므로 참고하자.

후기

DFS, BFS 에 대해서 깊이 생각해보지는 않았으나 글을 써내리면서 visited 처리나 ArrayDeque 가 더 좋은 이유에 대해서 새롭게 알 수 있어서 좋았다.

DFS 에서 Stack -> ArrayDeque 로 대체하고 BFS 에서 LinkedList -> ArrayDeque 로 대체되는 이유는 다시 글로 작성해보려고 한다.