그래프 - 깊이 우선 탐색 (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가 수행하게 만들었다.

 

#4 요약

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