Kotlin에서 그래프 탐색 알고리즘 구현하기: DFS와 BFS

그래프 탐색 알고리즘은 그래프의 모든 노드를 체계적으로 탐색하는 기술로, 많은 컴퓨터 과학 문제를 해결하는 데 사용됩니다. 대표적인 그래프 탐색 알고리즘으로 깊이 우선 탐색(DFS, Depth-First Search)과 너비 우선 탐색(BFS, Breadth-First Search)이 있습니다. 이 글에서는 Kotlin을 활용하여 이 두 탐색 알고리즘을 구현하는 방법을 소개하겠습니다.

깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS)은 가장 깊은 노드를 우선적으로 탐색하는 방식으로, 스택이나 재귀를 사용하여 구현할 수 있습니다. Kotlin에서의 DFS 구현 예제는 다음과 같습니다:

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

    fun addEdge(v: Int, w: Int) {
        adjList[v].add(w)
    }

    fun DFS(start: Int) {
        val visited = BooleanArray(vertices) { false }
        DFSUtil(start, visited)
    }

    private fun DFSUtil(v: Int, visited: BooleanArray) {
        visited[v] = true
        print("$v ")

        for (i in adjList[v]) {
            if (!visited[i]) {
                DFSUtil(i, visited)
            }
        }
    }
}

 

너비 우선 탐색(BFS)

너비 우선 탐색(BFS)은 가장 가까운 노드를 우선적으로 탐색하는 방식으로, 큐를 사용하여 구현합니다. Kotlin에서의 BFS 구현 예제는 다음과 같습니다:

import java.util.LinkedList

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

    fun addEdge(v: Int, w: Int) {
        adjList[v].add(w)
    }

    fun BFS(start: Int) {
        val visited = BooleanArray(vertices) { false }
        val queue: LinkedList<Int> = LinkedList()

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

        while (queue.isNotEmpty()) {
            val s = queue.poll()
            print("$s ")

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

 

DFS와 BFS의 선택

DFS와 BFS는 각각 다른 특성과 용도를 가지고 있습니다. DFS는 경로의 존재 여부, 순환 구조 확인, 퍼즐 게임의 해결 등에 유용하며, BFS는 최단 경로 문제, 레벨 별 탐색, 소셜 네트워킹 응용 프로그램 등에 적합합니다. 실제 문제 해결에 있어 어떤 탐색 알고리즘을 선택할지는 문제의 요구 사항과 특성에 따라 결정되어야 합니다.

 

Kotlin을 이용한 그래프 탐색 알고리즘 구현은 그래프 기반 문제 해결에 있어 강력한 도구를 제공합니다. Kotlin의 간결한 문법과 풍부한 표준 라이브러리는 개발자가 보다 직관적이고 효율적으로 알고리즘을 구현할 수 있게 도와줍니다. 이 글에서 소개된 DFS와 BFS 구현 방법을 시작으로, Kotlin을 활용한 다양한 그래프 알고리즘에 도전해 보시기 바랍니다.