코틀린 코딩테스트 강좌, 트리의 지름 구하기

안녕하세요. 오늘은 코틀린을 사용하여 트리의 지름을 구하는 방법에 대해 알아보겠습니다.
이 강좌에서는 트리의 기본 개념, 지름의 정의, 알고리즘 접근법에 대해 자세히 설명하고
예제 코드를 통해 실습해 볼 것입니다.

트리와 트리의 지름

트리는 각 노드가 0개 이상의 자식을 가지는 비선형 데이터 구조입니다.
트리는 다음과 같은 특성을 가집니다:

트리는 루트 노드를 가지며, 루트는 다른 노드와 연결됩니다.
자식 노드는 반드시 하나의 부모 노드를 가집니다.
루트에서 잎 노드까지의 경로가 트리의 높이를 정의합니다.

트리의 지름이란 트리내에서 가장 긴 경로의 길이를 의미합니다.
지름은 항상 두 잎 노드 간의 거리로 정의될 수 있습니다.
예를 들어, 아래와 같은 트리를 고려해보겠습니다:

이 트리의 지름은 노드 4에서 노드 5로 가는 최장 경로인 4-2-5입니다.
따라서 지름의 길이는 2입니다.

트리의 지름 구하기 알고리즘

지름을 구하기 위해서는 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)를 사용할 수 있습니다.
일반적으로 DFS가 더 많이 사용되는 방법입니다.
알고리즘의 기본 아이디어는 다음과 같습니다:

임의의 노드(루트 노드)를 선택하여 첫 번째 DFS를 수행합니다. 이때 가장 멀리 있는 노드를 찾습니다.
첫 번째 DFS에서 찾은 노드를 시작점으로 하여 두 번째 DFS를 수행합니다.
두 번째 DFS에서 계산된 최대 거리(지름)를 반환합니다.

코틀린 코드 구현

이제 이 알고리즘을 코틀린으로 구현해보겠습니다.
우리는 노드와 엣지를 표현하기 위해 데이터 클래스를 사용하고,
DFS 메서드를 만들어 트리의 지름을 계산하겠습니다.

데이터 클래스와 그래프 초기화

Kotlin
data class Edge(val to: Int, val weight: Int)

class Tree(val size: Int) {
    private val graph = Array(size) { mutableListOf() }

    fun addEdge(from: Int, to: Int, weight: Int) {
        graph[from].add(Edge(to, weight))
        graph[to].add(Edge(from, weight))
    }

    fun diameter(start: Int): Int {
        // 첫 번째 DFS 수행
        val (farthestNode, _) = dfs(start, BooleanArray(size), 0)
        // 두 번째 DFS 수행
        val (_, diameter) = dfs(farthestNode, BooleanArray(size), 0)
        return diameter
    }

    private fun dfs(node: Int, visited: BooleanArray, distance: Int): Pair {
        visited[node] = true
        var maxDistance = distance
        var farthestNode = node

        for (edge in graph[node]) {
            if (!visited[edge.to]) {
                val (newFarthestNode, newDistance) = dfs(edge.to, visited, distance + edge.weight)
                if (newDistance > maxDistance) {
                    maxDistance = newDistance
                    farthestNode = newFarthestNode
                }
            }
        }

        return Pair(farthestNode, maxDistance)
    }
}

코드 설명

– Edge 데이터 클래스: 엣지를 정의하는 클래스입니다.
노드와 가중치를 포함합니다.

– Tree: 트리를 표현하는 클래스입니다. 트리의 크기, 그래프 데이터 구조를 초기화합니다.
addEdge 메서드로 엣지를 추가할 수 있습니다.

– diameter 메서드: 지름을 계산하는 메서드입니다.
첫 번째 DFS와 두 번째 DFS를 수행합니다.

– dfs 메서드: 깊이 우선 탐색을 수행하는 재귀 메서드입니다.
방문한 노드를 체크하고 최대 거리를 계산합니다.
최대 거리를 기준으로 가장 먼 노드와 거리를 반환합니다.

테스트 케이스

트리의 지름을 테스트하기 위해 아래와 같이 엣지를 추가하고 결과를 출력해보겠습니다.

Kotlin
fun main() {
    val tree = Tree(5)
    tree.addEdge(0, 1, 1)
    tree.addEdge(0, 2, 2)
    tree.addEdge(1, 3, 1)
    tree.addEdge(1, 4, 1)

    val diameter = tree.diameter(0)
    println("트리의 지름은: $diameter")
}

실행 결과

    트리의 지름은: 4

마무리

이번 강좌에서는 코틀린을 활용하여 트리의 지름을 구하는 방법을 살펴보았습니다.
DFS를 사용한 이 접근 방법은 트리 데이터 구조를 다루는 데 유용하며,
다양한 응용 프로그램에서 활용될 수 있습니다.
트리 관련 문제를 해결하는 데 있어 이 강좌가 도움이 되기를 바랍니다.

앞으로도 다양한 알고리즘과 코딩 테스트 문제를 다룰 예정이니 많은 기대 부탁드립니다!
감사합니다.