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

#1 그래프의 탐색

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

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

#2 알고리즘

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

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

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

#3 코드 - 코틀린

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

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

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

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

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

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

(3) 매개변수 정점을 discovered에 추가하고, 방문...
bfs에 대해 다룬 이 게시글과의 일관성을 위해, Set형 변수 이름을 discovered라고 두었지만, 사실 이 코드에서 더 정확한 이름은 visited일 것이다. bfs에서와 달리 본 게시글(dfs)에서는, 어떤 정점을 Set에 넣음(add())과 동시에 해당 정점에 '방문'한 것으로 취급하기 때문이다. 

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

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

#4 요약

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