[백준/BOJ] 1967번: 트리의 지름

문제

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

해설

한 정점에서 가장 멀리 있는 정점은 원의 지름 즉, 테두리에 해당되는 정점이다.

따라서 한 정점에서 가장 멀리 있는 정점을 구한 후, 그 정점에서 가장 멀리 있는 정점까지의 길이가 곧 원의 지름이 된다.

우선 가장 멀리 있는 한개의 정점을 구해야 한다.

이때 어떠한 정점에서 출발을 하든지 간에 가장 멀리 있는 정점은 지름에 해당하는 정점 중 하나이다.

지름에 해당하는 한 정점을 구했다면, dfs에 사용된 방문여부 배열을 초기화해준 후, 그 정점으로부터 가장 먼 정점을 찾기 위한 dfs를 또 한번 수행하면 된다.

코드

private lateinit var tree: Array<ArrayList<Pair<Int, Int>>>
private lateinit var visited: BooleanArray
private var len = 0
private var endNode = 0

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    tree = Array(n + 1) { ArrayList() }
    visited = BooleanArray(n + 1)

    repeat(n - 1) {
        val (from, to, cost) = readLine().split(" ").map { it.toInt() }
        tree[from].add(Pair(to, cost))
        tree[to].add(Pair(from, cost))
    }

    dfs(6, 0)

    visited.fill(false)
    len = 0

    dfs(endNode, 0)
    println(len)
}

private fun dfs(node: Int, depth: Int) {
    if(visited[node]) return

    visited[node] = true
    if(len < depth) {
        len = depth
        endNode = node
    }

    for(i in tree[node].indices) {
        dfs(tree[node][i].first, depth + tree[node][i].second)
    }
}