백준 [1967] kotlin

[문제]

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

1967번: 트리의 지름

[풀이]

DFS를 이용하여 풀었다.

DFS의 과정은 아래와 같다.

 

테스트 케이스만 보고 이진트리라고 생각하면 안된다. 

 

정답을 저장한 변수를 0으로 초기화를 한다.

 

<과정>

1. 더 이상 이동할 자식 노드가 없다면 0을 반환해준다.

2. 자식이 하나만 있다면

• 자식의 가중치 + (자식을 기준으로 DFS) 의 값이 현재 노드 위치에서의 가장 긴 지름이다.
• 정답은, 지름을 찾아야 하므로 트리 전체에서의 가장 긴 지름을 찾아야 하므로 정답과 현재 노드의 지름의 크기를 비교하여 새롭게 갱신을 해준다.

3. 자식이 1명 이상 있다면

• 현재 노드의 자식 숫자만큼 자식의 가중치 + (자식을 기준으로 DFS) 과정을 반복하여, 반환값을 배열에 저장을 해준다.
• 배열을 오름차순으로 정렬을 해주면, 왼쪽 기준 배열에 두 개의 값을 더 해주면 현재 노드의 지름이다.
• 이렇게 구한 현재 노드의 지름을 정답과 비교하여 새롭게 갱신을 해준다.

[코드]

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.max

lateinit var tree : ArrayList<ArrayList<Pair<Int,Int>>>
var ans = 0
fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))
    var n = br.readLine().toInt()
    tree = ArrayList()
    repeat(n+1){ tree.add(ArrayList())}
    repeat(n-1)
    {
        val route = br.readLine().split(" ").map{it.toInt()}
        tree[route[0]].add(Pair(route[1],route[2]))
    }

    dfs(1)
    bw.write(ans.toString())
    bw.flush()
    bw.close()
}
fun dfs(node : Int) : Int
{
    /* 자식이 없는 경우 */
    if(tree[node].isEmpty()) return 0

    /* 자식이 1명만 있는 경우 */
    if(tree[node].size == 1) {
        val tmp = tree[node][0].second + dfs(tree[node][0].first)
        ans = max(tmp,ans)
        return tmp
    }
    
    /* 자식이 1명 이상인 경우 */
    var pq = ArrayList<Int>()
    repeat(tree[node].size)
    {
        i ->
        pq.add(tree[node][i].second + dfs(tree[node][i].first))

    }
    pq.sortDescending()
    ans = max(pq[0] + pq[1], ans)
    return pq[0]
}