[백준] 트리의 지름 (1167)(kotlin)

문제 설명

백준 1167번 문제 링크 풀이 참고

입력 및 출력

» 입력

• 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다. 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

» 출력

첫째 줄에 트리의 지름을 출력한다.

예제 입출력(테스트케이스)

입력	출력
5 1 3 2 -1 2 4 4 -1 3 1 2 4 3 -1 4 2 4 3 3 5 6 -1 5 4 6 -1	11

문제 풀이1

import java.util.Scanner

var list = arrayOf<ArrayList<Node>>()
var visited = booleanArrayOf()
var max = 0
var node = 0

fun main() {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    list = Array(n + 1) { arrayListOf<Node>() }

    for (i in 0 until n) {
        val s = sc.nextInt()
        while (true) {
            val e = sc.nextInt()
            if (e == -1) break

            val cost = sc.nextInt()
            list[s].add(Node(e, cost))
        }
    }

    visited = BooleanArray(n + 1)
    dfs(4, 0)

    visited.fill(false)
    dfs(node, 0)

    println(max)
}

fun dfs(x: Int, len: Int) {
    if (len > max) {
        max = len
        node = x
    }

    visited[x] = true

    for (current in list[x]) {
        if (!visited[current.e]) {
            dfs(current.e, current.cost + len)
        }
    }
}

class Node {
    var e: Int = 0
    var cost: Int = 0

    constructor(e: Int, cost: Int) {
        this.e = e
        this.cost = cost
    }
}