[kotlin] 코틀린으로 깊이 우선 탐색 알고리즘 구현하기

14 Dec 2023

kotlin

깊이 우선 탐색(Depth First Search, DFS) 알고리즘은 그래프에서 깊이를 우선으로 탐색하는 알고리즘입니다. 즉, 한 정점에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색합니다. 이번 글에서는 코틀린으로 깊이 우선 탐색 알고리즘을 구현하는 방법에 대해 알아보겠습니다.

그래프 표현하기

그래프를 표현하는 가장 간단한 방법은 인접 리스트를 사용하는 것입니다. 인접 리스트는 그래프의 각 정점마다 해당 정점과 연결된 다른 정점들의 리스트를 저장하는 방식입니다.

class Graph(val n: Int) {
    private val adj = Array(n) { mutableListOf<Int>() }

    fun addEdge(u: Int, v: Int) {
        adj[u].add(v)
    }
}

위의 코드는 정점의 개수 n을 인자로 받아 인접 리스트를 저장하는 adj 배열을 초기화하는 Graph 클래스를 보여줍니다. addEdge 메서드를 사용하여 간선을 추가할 수 있습니다.

깊이 우선 탐색 구현하기

이제 인접 리스트를 사용하여 깊이 우선 탐색 알고리즘을 구현해보겠습니다. 재귀적으로 구현할 수 있습니다.

fun dfs(graph: Graph, v: Int, visited: BooleanArray) {
    visited[v] = true
    print("$v ")

    for (u in graph.adj[v]) {
        if (!visited[u]) {
            dfs(graph, u, visited)
        }
    }
}

dfs 함수는 현재 정점 v를 방문하고, 해당 정점과 연결된 방문하지 않은 정점을 재귀적으로 방문하는 방식으로 동작합니다.

테스트해보기

이제 위에서 구현한 깊이 우선 탐색 알고리즘을 테스트해보겠습니다.

fun main() {
    val graph = Graph(4)
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 2)
    graph.addEdge(2, 0)
    graph.addEdge(2, 3)
    graph.addEdge(3, 3)

    val visited = BooleanArray(4)
    dfs(graph, 2, visited)
}

위의 코드는 4개의 정점과 6개의 간선으로 이루어진 그래프를 만들고, 정점 2에서 깊이 우선 탐색을 시작하는 예제입니다.

마무리

이제 여러분은 코틀린으로 깊이 우선 탐색 알고리즘을 구현하는 방법에 대해 알게 되었습니다. 깊이 우선 탐색은 그래프에서 특정 경로를 찾거나 순회할 때 유용한 알고리즘 중 하나입니다.