[kotlin] 깊이 우선 탐색(Depth-First Search)의 자료 구조 선택

08 Dec 2023

kotlin

깊이 우선 탐색은 그래프나 트리에서 한 정점으로부터 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 알고리즘입니다. 이를 구현하기 위해서는 어떤 자료 구조를 선택해야 할까요? 여기에는 몇 가지 선택지가 있습니다.

스택(Stack)

스택을 활용하여 깊이 우선 탐색을 구현할 수 있습니다. 스택은 후입선출(LIFO, Last In First Out) 구조로, 마지막으로 삽입된 항목이 가장 먼저 꺼내지는 자료 구조입니다. 깊이 우선 탐색의 구현에서는 현재 정점에서 이동 가능한 모든 경로를 탐색해야 하므로, 현재 경로를 스택에 보관하고 다음에 탐색할 경로를 차례로 스택에 넣는 방식으로 구현할 수 있습니다.

fun depthFirstSearch(graph: Graph, startVertex: Vertex) {
    val stack = Stack<Vertex>()
    val visited = HashSet<Vertex>()

    stack.push(startVertex)

    while (!stack.isEmpty()) {
        val currentVertex = stack.pop()
        if (!visited.contains(currentVertex)) {
            visited.add(currentVertex)
            for (vertex in graph.getAdjacentVertices(currentVertex)) {
                if (!visited.contains(vertex)) {
                    stack.push(vertex)
                }
            }
        }
    }
}

재귀 함수(Recursion)

또 다른 방법으로는 재귀 함수를 사용하여 깊이 우선 탐색을 구현하는 것입니다. 깊이 우선 탐색을 재귀적으로 구현할 경우, 현재 정점에서 이동 가능한 경로가 존재하면 해당 경로로 이동하여 다시 탐색을 시작합니다.

fun depthFirstSearch(graph: Graph, currentVertex: Vertex, visited: HashSet<Vertex>) {
    visited.add(currentVertex)
    for (vertex in graph.getAdjacentVertices(currentVertex)) {
        if (!visited.contains(vertex)) {
            depthFirstSearch(graph, vertex, visited)
        }
    }
}

결론

깊이 우선 탐색의 자료 구조 선택은 스택이나 재귀 함수 중에 선택할 수 있습니다. 둘 다 동일한 목적을 달성할 수 있지만, 각각의 장단점을 고려하여 상황에 맞게 선택해야 합니다.

깊이 우선 탐색 알고리즘은 그래프나 트리를 탐색할 때 매우 유용한데, 자료 구조를 선택하는 것은 알고리즘의 성능에 큰 영향을 미치므로 신중하게 고려해야 합니다.