백준 [1167] kotlin

[문제]

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

1167번: 트리의 지름

[풀이]

이 문제는 아래의 문제와 거의 같은 문제라고 볼 수 있다.

https://shino72.tistory.com/entry/%EB%B0%B1%EC%A4%80-1967-kotlin

백준 [1967] kotlin

 

위의 문제의 풀이 방식과 거의 유사한데, 다른 점이 있다면 

1967 문제의 경우에는 입력으로 한 방향으로만 주어지지만, 1167 문제의 경우에는 1->3, 3->1과 같이 노드 1과 3이 연결되어 있다는 정보를 양방향으로 알려주기 때문에, 위의 방식으로 100프로 동일하게 풀면, 1->3으로 이동하고 3->1로 이동하여 사이클이 발생해 에러가 발생하게 된다.

이를 해결하기 위해, 방문한 노드를 다시 방문하지 않도록 visit이라는 배열을 만들어 체크를 해주면 된다. 

 

주의할 점이 있다면, 이 문제의 입력으로 주어지는 노드는 1,2,3,4,5... 숫자 순으로 주어지는 것이 아니라, 랜덤으로 주어지기 때문에 트리를 만들때 이 점만 주의를 해주면 쉽게 풀 수 있는 문제이다.

 

위에 설명 외에 자세한 풀이방법은 위의 링크를 참고하면 될 것 같다.

 

[코드]

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>>>
lateinit var visit : BooleanArray
var ans = 0
var V = 0
fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))

    tree = arrayListOf()
    V = br.readLine().toInt()
    repeat(V){tree.add(arrayListOf())}
    repeat(V)
    {
        val tmp = br.readLine().split(" ").map{it.toInt()}
        val idx = tmp[0]-1
        for (j in 0 until (tmp.size/2-1))
        {
            tree[idx].add(Pair(tmp[j*2+1],tmp[j*2+2]))
        }
    }
    visit = BooleanArray(V){false}
    visit[0] = true
    dfs(0)
    bw.write(ans.toString())
    bw.flush()
    bw.close()
}

fun dfs(idx : Int) : Int
{
    if(idx == V) return 0

    if(tree[idx].size == 1)
    {
        if(visit[tree[idx][0].first - 1]) return 0
        visit[tree[idx][0].first-1] = true
        val tmp = tree[idx][0].second + dfs(tree[idx][0].first-1)
        ans = max(ans, tmp)
        return tmp
    }
    var pq = ArrayList<Int>()
    repeat(tree[idx].size)
    {
        i ->
        if(!visit[tree[idx][i].first - 1])
        {
            visit[tree[idx][i].first-1] = true
            pq.add(tree[idx][i].second + dfs(tree[idx][i].first-1))
        }
    }
    if(pq.size==0) return 0
    if(pq.size==1) {
        ans = max(pq[0],ans)
        return pq[0]
    }
    pq.sortDescending()
    ans = max(pq[0] + pq[1], ans)
    return pq[0]
}