[kotlin] 코틀린 집합(Set)을 이용한 그래프 탐색

08 Dec 2023

kotlin

그래프는 정점과 정점 사이를 연결하는 간선으로 이루어진 자료 구조로, 다양한 문제에 활용됩니다. 그래프를 탐색하는 방법 중 하나는 깊이 우선 탐색(DFS, Depth-First Search)입니다. 이 접근 방식은 깊이를 우선하여 모든 정점을 탐색하는 알고리즘이며, 재귀적으로 구현할 수 있습니다.

코틀린에서는 집합(Set)을 이용하여 그래프의 정점과 간선을 표현할 수 있습니다. 이번 예제에서는 코틀린을 사용하여 DFS 알고리즘을 구현하고, 그래프를 탐색하는 방법을 알아보겠습니다.

그래프 표현하기

그래프를 표현하기 위해 정점과 간선을 관리하는 방법이 있습니다. 여기에서는 인접 리스트를 이용하여 그래프를 표현해보겠습니다. 코틀린의 Set을 사용하여 한 정점에서 다른 정점으로의 간선을 연결할 수 있습니다.

예를 들어, 다음과 같이 그래프를 표현할 수 있습니다.

val graph = mapOf<Int, Set<Int>>(
to setOf(2, 3),
to setOf(1, 4, 5),
to setOf(1),
to setOf(2),
to setOf(2)
)

위 코드에서 mapOf를 사용하여 각 정점과 이어진 간선을 표현하고 있습니다.

DFS 알고리즘 구현하기

이제 DFS 알고리즘을 구현해보겠습니다. DFS는 재귀적으로 동작하기 때문에 임의의 시작 정점부터 방문이 가능한 모든 정점을 순회할 수 있습니다.

fun dfs(vertex: Int, visited: MutableSet<Int>, graph: Map<Int, Set<Int>>) {
    if (!visited.contains(vertex)) {
        visited.add(vertex)
        println("Visiting vertex $vertex")
        for (v in graph[vertex]!!) {
            dfs(v, visited, graph)
        }
    }
}

위 코드에서 dfs 함수는 시작 정점 vertex와 방문한 정점을 추적하는 visited 집합, 그리고 그래프를 나타내는 graph 맵을 입력으로 받습니다. 재귀적으로 정점을 방문하며, 이미 방문한 정점은 visited에 추가하여 다시 방문하지 않도록 합니다.

예제

다음은 DFS 알고리즘을 적용한 예제 코드입니다.

val graph = mapOf<Int, Set<Int>>(
    1 to setOf(2, 3),
    2 to setOf(1, 4, 5),
    3 to setOf(1),
    4 to setOf(2),
    5 to setOf(2)
)

fun main() {
    val startVertex = 1
    val visited = mutableSetOf<Int>()
    dfs(startVertex, visited, graph)
}

위 코드에서는 시작 정점을 1로 설정하고, dfs 함수를 호출하여 그래프를 탐색하고 방문한 정점을 출력합니다.

위 예제를 통해 코틀린을 사용하여 집합(Set)을 이용한 그래프 탐색 및 DFS 알고리즘을 구현하는 방법을 알아보았습니다. 이를 통해 다양한 그래프 문제를 해결하는 데 활용할 수 있습니다.

참고 문헌:

https://en.wikipedia.org/wiki/Depth-first_search