[kotlin] 코틀린으로 너비 우선 탐색 알고리즘 작성하기

14 Dec 2023

kotlin

너비 우선 탐색 알고리즘이란 그래프에서 가까운 노드부터 탐색하는 알고리즘으로, 주어진 그래프에서 시작 노드로부터 깊이 1씩 증가하면서 탐색을 진행합니다.

코틀린으로 너비 우선 탐색 알고리즘 작성하기

아래는 코틀린을 사용하여 너비 우선 탐색 알고리즘을 작성하는 간단한 예제입니다.

class Graph {
    private val adjList: MutableMap<Int, MutableList<Int>> = mutableMapOf()

    fun addEdge(u: Int, v: Int) {
        adjList.computeIfAbsent(u) { mutableListOf() }.add(v)
        adjList.computeIfAbsent(v) { mutableListOf() }.add(u)
    }

    fun bfs(startNode: Int) {
        val visited = MutableList(adjList.size) { false }
        val queue: MutableList<Int> = mutableListOf()

        visited[startNode] = true
        queue.add(startNode)

        while (queue.isNotEmpty()) {
            val node = queue.removeFirst()
            print("$node ")

            for (neighbor in adjList[node]!!) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true
                    queue.add(neighbor)
                }
            }
        }
    }
}

fun main() {
    val graph = Graph()
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 2)
    graph.addEdge(2, 0)
    graph.addEdge(2, 3)
    graph.addEdge(3, 3)
    println("너비 우선 탐색 결과:")
    graph.bfs(2)
}

위 코드는 인접 리스트를 이용하여 그래프를 구현하고, 너비 우선 탐색 알고리즘을 구현한 것입니다.

이제 코틀린으로 간단한 그래프에서 너비 우선 탐색을 수행하는 방법을 알 수 있었습니다. 이를 응용하여 더 복잡한 그래프에서도 너비 우선 탐색을 적용할 수 있을 것입니다.

참고 자료

코틀린 공식 문서: Kotlin
그래프 이론에 대한 자세한 내용: Graph Theory