백준 1167 트리의 지름 Kotlin (dfs)

문제 출처 : https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

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

출력

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

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• 깊이 우선 탐색

풀이

주어진  트리의 지름(임의의 두 점 사이의 거리 중 가장 긴 것)을 구하는 방법은 다음과 같다.

 

1. 임의의 점을 선택한 후 임의의 점에서 가장 멀리 있는(가중치의 합이 가장 큰)점 x를 찾는다.

2. x에서 가장 멀리 있는 점까지의 거리가 트리의 지름이다.

 

위의 트리의 지름을 구하는 방법만 알면 쉽게 풀 수 있는 문제이다.

dfs로 임의의 점을 선택해서 임의의 점에서 가장 멀리 있는 점을 찾고,

또 한번 dfs로 가장 멀리 있는 점에서 가장 멀리 있는 점의 거리를 찾으면 된다.

 

이렇게 간단한 문제지만 4%에서 틀리는 경우가 많은데 이는 입력에 함정이 있기 때문이다(본인도 고생했다)

예제에서는 5개의 정점이 순서대로 1, 2, 3, 4 ,5 이렇게 입력이 주어졌지만 순서대로 주어진다는 보장이 없다.

V가 5일 때, 3, 1, 4, 2, 5 이런 식으로 입력이 주어질 수 있다는 것이다..!!!!!!!

 

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer
import kotlin.math.*

var end =0
var answer=0
fun dfs(edge : Array<ArrayList<Distance>>, visited : BooleanArray, node : Int, dis : Int){
    visited[node]=true
    if(answer <dis){
        answer = dis
        end = node
    }

    for( i in 0 until edge[node].size){
        val nextDis = dis + edge[node][i].dis
        val next = edge[node][i].node
        if(visited[next])continue
        dfs(edge,visited,next,nextDis)
    }
}

fun main() = with(System.out.bufferedWriter()){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val V = Integer.parseInt(br.readLine())
    val edge = Array(V+1,{ArrayList<Distance>()})
    var visited = BooleanArray(V+1,{false})
    for( i in 0 until V){
        val tk =StringTokenizer(br.readLine())
        val node =Integer.parseInt(tk.nextToken())
        while(true){
            val to = Integer.parseInt(tk.nextToken())
            if(to ==-1)break
            val dis = Integer.parseInt(tk.nextToken())
            edge[node].add(Distance(to,dis))
        }
    }
    dfs(edge,visited,1,0)
    visited = BooleanArray(V+1,{false})
    dfs(edge,visited,end,0)
    write("$answer")
    close()
}
data class Distance(val node :Int, val dis : Int)