Kotlin을 활용한 그래프 알고리즘의 구현과 적용

그래프는 노드(Node)들과 이들 사이의 연결을 표현하는 간선(Edge)들로 구성된 구조로, 다양한 실세계 문제를 모델링하는 데 사용됩니다. 컴퓨터 과학에서 그래프 알고리즘은 경로 탐색, 네트워크 흐름, 최소 스패닝 트리 등과 같은 문제를 해결하는 데 필수적입니다. Kotlin 언어의 강력한 표현력과 간결한 문법을 활용하여 그래프 알고리즘을 구현하는 방법을 살펴보겠습니다. 이 글에서는 그래프의 표현 방법, 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)에 대해 설명합니다.

그래프의 표현

그래프는 주로 인접 리스트나 인접 행렬을 사용하여 표현됩니다. Kotlin에서 인접 리스트로 그래프를 표현하는 방법은 다음과 같습니다:

class Graph(val vertices: Int) {
    val adjListArray: MutableList<MutableList<Int>> = MutableList(vertices) { mutableListOf<Int>() }

    fun addEdge(src: Int, dest: Int) {
        adjListArray[src].add(dest)
        // 무향 그래프의 경우, 다음 줄도 추가합니다:
        // adjListArray[dest].add(src)
    }
}

 

이 코드는 각 노드에서 다른 노드로의 간선 정보를 저장하는 인접 리스트를 생성합니다.

깊이 우선 탐색 (DFS)

깊이 우선 탐색(DFS)은 그래프의 노드를 탐색하는 알고리즘으로, 한 방향으로 갈 수 있는 한 깊게 탐색한 다음, 다른 방향으로 탐색을 계속하는 방법입니다.

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

    for (next in graph.adjListArray[v]) {
        if (!visited[next]) dfsUtil(next, visited, graph)
    }
}

fun dfs(graph: Graph, startVertex: Int) {
    val visited = BooleanArray(graph.vertices)
    dfsUtil(startVertex, visited, graph)
}

 

너비 우선 탐색 (BFS)

너비 우선 탐색(BFS)은 가장 가까운 노드를 우선적으로 탐색하는 방법으로, 한 노드에서 인접한 모든 노드를 방문한 후, 방문한 노드들에서 다시 인접한 노드를 탐색합니다.

fun bfs(graph: Graph, startVertex: Int) {
    val visited = BooleanArray(graph.vertices)
    val queue: MutableList<Int> = mutableListOf()

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

    while (queue.isNotEmpty()) {
        val v = queue.removeAt(0)
        print("$v ")

        for (next in graph.adjListArray[v]) {
            if (!visited[next]) {
                visited[next] = true
                queue.add(next)
            }
        }
    }
}

 

Kotlin에서 그래프 알고리즘을 구현하는 것은 그래프 기반 문제를 해결하는 데 있어 강력한 도구를 제공합니다. DFS와 BFS는 그래프 탐색의 가장 기본적인 알고리즘으로, 다양한 문제 해결의 기초가 됩니다. 이러한 알고리즘을 이해하고 Kotlin으로 구현하는 방법을 익히면, 실세계 문제에 적용할 수 있는 효과적인 해결 방법을 개발할 수 있습니다.