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

#1 그래프의 탐색

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

그래프의 각 정점을 한번씩 방문할 필요가 있다고 해보자. 그 방문의 방법에는 크게 2가지 방법이 있다. 하나는 깊이 우선 탐색이다. 또 다른 하나는 너비 우선 탐색이다. 본 게시글에서는 깊이 우선 탐색법을 다룬다. (너비 우선 탐색에 대해서는 이 게시글에서 다룬다)
 

#2 알고리즘

https://commons.wikimedia.org/wiki/File:Depth-first-tree.svg

원래라면 순서도를 통해 알고리즘을 소개하고 코드로 넘어가는 편이 이해하기 좋지만, 그래프 탐색 알고리즘은 그냥 코드부터 보는 게 오히려 이해가 더 빠르다고 생각한다. 다만, 인접 배열 (Adjacency Array)의 지식에 대해서는 알고 있어야 한다는 전제 하다. 여기서 사용할 인접 배열은 이 게시글에 있다 (가중치가 없는 무향 그래프).

대신 왜 '깊이 우선' 탐색이라는 이름이 붙었는지는 설명할 가치가 있다. 깊이 우선 탐색은 다른 말로 '첫번째 자식 우선' 탐색이다. 일반적으로 그래프는 깊이의 높낮이가 위 그래프처럼 y축과 평행하게 그려진다. 따라서 '첫번째 자식 우선'으로 탐색한다는 말은, 2 → 3 → 4 → 5 → 6 → 7 → 8와 같은 식으로 탐색한다는 말이 된다. 이 탐색은 y축(높이)를 우선해 이동하는 모양이 된다 (x축 이동은 y축 탐색이 종료된 후에 시행된다. 우선순위가 아닌 것이다). 그래서 깊이 우선 탐색이라 부른다.
 

#3 코드 - 코틀린

#3-1 기본 코드

fun main() {
    // (1) listOfAdjacencyArray[n]이 가지는 의미를 알아야 한다 (설명 참조)
    val listOfAdjacencyArray = listOf(
        arrayOf(1, 2),
        arrayOf(0, 3, 4),
        arrayOf(0, 4),
        arrayOf(1),
        arrayOf(1, 2)
    )

    // (2) visited는 방문이 완료된 정점들을 기록하는 Set(집합)이다
    val visited = mutableSetOf<Int>()
    dfs(listOfAdjacencyArray, 0, visited)  // 0번 정점(vertex)에서 탐색 시작
}

fun dfs(listOfAdjacencyArray: List<Array<Int>>, vertex: Int, visited: MutableSet<Int>) {
    // (3) 매개변수 정점을 visited에 추가하고, 방문해서 진행할 일을 수행한다. 여기선 doSomethingFunction()으로 표현했다
    visited.add(vertex)
//  doSomethingFunction(vertex)
    println("Visit complete: $vertex")

    // (4) 정점의 이웃 정점마다 (5)을 수행
    for (neighborVertex in listOfAdjacencyArray[vertex]) {
        // (5) visited 목록에 없다면, 이웃 정점을 재귀 호출한다
        if (neighborVertex !in visited) {
            dfs(listOfAdjacencyArray, neighborVertex, visited)
        }
    }
}

(1) listOfAdjacencyArray[n]이 가지는 의미를 알아야 한다
정점에 부여된 번호가 0 ~ N일 때, listOfAdjacencyArray[n]은 n번 정점에 연결된 이웃(neighbor) 정점들의 배열을 의미한다.

(2) visited는 방문이 완료된 정점들을 기록하는 Set(집합)이다
bfs와 달리 visited가 밖에 나와 있다. dfs의 구조(재귀 호출) 때문에 그렇다

(3) 매개변수 정점을 visited에 추가하고, 방문...
bfs에 대해 다룬 이 게시글과 달리, Set형 변수 이름을 visited라고 두었다. bfs에서와 달리 본 게시글(dfs)에서는, 어떤 정점을 Set에 넣음(add())과 동시에 해당 정점에 '방문'한 것으로 취급하기 때문이다. 

(4) 정점의 이웃 정점마다 (5)을 수행
listOfAdjacencyArray[n]은 방금 방문 완료한 정점 n에 연결된 이웃 정점들의 배열이다. 이 배열의 요소마다 (5)을 수행한다.

(5) visited 목록에 없다면, 이웃 정점을 재귀 호출한다
재귀 호출을 수행한다. 재귀 호출은 스택 구조를 이룬다. 즉, 가장 늦게(최근에) 재귀 호출된 dfs()가 먼저 처리된다 (후입 선출). #2에서 깊이 우선 탐색을 '첫번째 자식 우선' 탐색이라고 말한 이유다. 각 재귀 호출은 listOfAdjacencyArray[vertex]의 첫번째 원소 즉 listOfAdjacencyArray[vertex][0]부터 수행된다. 또, 해당 재귀 호출에서 연쇄적으로 발생할 재귀 호출 또한 마찬가지로 인접 배열에 적힌 첫번째 원소부터 수행될 것이다.

#3-2 제네릭을 이용한 코드

import kotlin.collections.HashMap

fun main() {
    // (1) mapOfAdjacencyArray[n]이 가지는 의미를 알아야 한다 (설명 참조)
    val mapOfAdjacencyArray = HashMap<String, Array<String>>()
    mapOfAdjacencyArray["강아지"] = arrayOf("고양이", "사슴")
    mapOfAdjacencyArray["고양이"] = arrayOf("강아지", "코뿔소", "흰머리오목눈이")
    mapOfAdjacencyArray["사슴"] = arrayOf("강아지", "흰머리오목눈이")
    mapOfAdjacencyArray["코뿔소"] = arrayOf("고양이")
    mapOfAdjacencyArray["흰머리오목눈이"] = arrayOf("고양이", "사슴")

    // (2) visited는 방문이 완료된 정점들을 기록하는 Set(집합)이다
    val visited = mutableSetOf<String>()
    dfs(mapOfAdjacencyArray, "강아지", visited)  // "강아지" 정점(vertex)에서 탐색 시작
}

fun <T> dfs(mapOfAdjacencyArray: Map<T, Array<T>>, vertex: T, visited: MutableSet<T>) {
    // (3) 매개변수 정점을 visited에 추가하고, 방문해서 진행할 일을 수행한다. 여기선 doSomethingFunction()으로 표현했다
    visited.add(vertex)
//  doSomethingFunction(vertex)
    println("Visit complete: $vertex")

    // (4) 정점의 이웃 정점마다 (5)을 수행
    for (neighborVertex in mapOfAdjacencyArray[vertex]!!) {
        // (5) visited 목록에 없다면, 이웃 정점을 재귀 호출한다
        if (neighborVertex !in visited) {
            dfs(mapOfAdjacencyArray, neighborVertex, visited)
        }
    }
}

지금까지 정점을 편의상 Int형이라고만 다뤘지만, 정점을 구분하는 기준이 다른 데이터형일 수도 있다. 그 경우에 사용할 수 있도록 제네릭을 이용해 리팩토링한 코드다. listOfAdjacencyArray가 mapOfAdjacencyArray로 바뀐 것에도 주목하자. listOfAdjacencyArray의 index는 반드시 Int여야 한다는 제약 조건이 있기에 이 index의 역할을, mapOfAdjacencyArray의 key가 수행하게 만들었다.
 

#3-3 백트래킹 (Backtracking)

개념
백트래킹(Backtracking)이란 백트래킹은 모든 가능한 경우의 수를 탐색하되, 불가능하거나 정답이 될 수 없는 경우는 빨리 포기(가지치기) 하고 돌아오는 기법을 의미한다. 가령, 아래의 코드는 "강아지"로부터 "흰머리오목눈이"까지 갈 수 있는 있는 모든 경로의 수를 찾는 코드다 (단, 한 번 방문한 정점은 다시 방문할 수 없음).
 
코드와 설명

// 경로 탐색 문제라는 가정 하의 코드이므로 선언된 변수들
val start = "강아지"
val goal = "흰머리오목눈이"
val path = mutableListOf<String>()

fun main() {
    // (1) mapOfAdjacencyArray[n]이 가지는 의미를 알아야 한다 (설명 참조)
    val mapOfAdjacencyArray = HashMap<String, Array<String>>()
    mapOfAdjacencyArray["강아지"] = arrayOf("고양이", "사슴")
    mapOfAdjacencyArray["고양이"] = arrayOf("강아지", "코뿔소", "흰머리오목눈이")
    mapOfAdjacencyArray["사슴"] = arrayOf("강아지", "흰머리오목눈이")
    mapOfAdjacencyArray["코뿔소"] = arrayOf("고양이")
    mapOfAdjacencyArray["흰머리오목눈이"] = arrayOf("고양이", "사슴")

    // (2) visited는 방문이 완료된 정점들을 기록하는 Set(집합)이다
    val visited = mutableSetOf<String>()

    println("모든 경로:") // 경로 탐색 문제라는 가정 하의 코드이므로.
    dfs(mapOfAdjacencyArray, start, visited)  // start 정점(vertex)에서 탐색 시작
}

fun <T> dfs(mapOfAdjacencyArray: Map<T, Array<T>>, vertex: T, visited: MutableSet<T>) {
    // (3) 매개변수 정점을 visited에 추가하고, 방문해서 진행할 일을 수행한다. 여기선 doSomethingFunction()으로 표현했다
    visited.add(vertex)
    doSomethingFunction(vertex)
//  println("Visit complete: $vertex") // 콘솔 창이 더러워지므로, 생략

    if (vertex == goal) { // 경로 탐색 문제라는 가정 하의 코드이므로 선언된 if문.
        println(path)
    } else {
        // (4) 정점의 이웃 정점마다 (5)을 수행
        for (neighborVertex in mapOfAdjacencyArray[vertex]!!) {
            // (5) visited 목록에 없다면, 이웃 정점을 재귀 호출한다
            if (neighborVertex !in visited) {
                dfs(mapOfAdjacencyArray, neighborVertex, visited)
            }
        }
    }

    visited.remove(vertex) // 백트래킹
    doSomethingFunction2() // 백트래킹 후 할 일. 여기선 doSomethingFunction2()로 표현함.
}

fun <T> doSomethingFunction(vertex: T) {
    path.add(vertex.toString())
}

fun doSomethingFunction2() {
    path.removeAt(path.size - 1)
}

/* 출력 결과

모든 경로:
[강아지, 고양이, 흰머리오목눈이]
[강아지, 사슴, 흰머리오목눈이]

*/

위에서 쉽게 설명하려고 백트래킹을 '포기', '가지치기'라는 단어를 통해 설명했지만, 사실 포기라기보단 '되돌아감', '초기화'에 가깝다. '가지치기'의 늬앙스처럼 완전하게 버려 배제하는 것은 아니기 때문이다. 좀 더 와닿도록 비유를 하자면, Ctrl +  Z를 통한 되돌리기(Undo)다. 그러나 위 코드를 봐도, 백트래킹의 어떤 동작인지에 대한 느낌은 알겠지만 그 동작을 직관적으로 이해했다고까지 하긴 힘들 것이다. 그렇다면 아래를 참조하자.
 
백트래킹이 필요한데 수행하지 않으면 생기는 일

[백준] 26169 (세 번 이내에 사과를 먹자)

위는 백트래킹이 가미된 DFS 문제에 대해 다룬 게시글이다. 또, 이 게시글의 '실패한 코드' 부분에 백트래킹이 필요한 이유가 도식도를 통해 직관적으로 설명되어있다.
 

#4 요약

깊이 우선 탐색은 인접 배열의 원소들을 (재귀 호출 구조라는) Stack에 넣는다.