백준 1167번 트리의 지름 with Kotlin

트리의 지름 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

256 MB

20750

7508

5409

34.562%

문제

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

입력

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

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

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

11

출처

• 문제의 오타를 찾은 사람: ababc1005, cfghj101, WeissBlume
• 문제를 만든 사람: author5
• 데이터를 추가한 사람: djm03178

알고리즘 분류

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

https://blog.myungwoo.kr/112

트리의 지름 구하기

 

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
 
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
val n = readLine()!!.toInt()
val graph = MutableList(n+1,{ mutableListOf<Int>()})
var tmp = 0
val dist = MutableList(n+1,{ mutableListOf<Int>()})
var visit = BooleanArray(n+1){false}
var ans = Int.MIN_VALUE
var point = 0
fun main()=with(br){
    for(i in 0 until n){
        var line = readLine()!!.split(" ").map{it.toInt()}
        var a = line[0]
        for(j in 1 until line.size){
            if(line[j]==-1){
                break
            }
            else{
                if(j%2==1){
                    graph[a].add(line[j])
                }
                else if(j%2==0){
                    dist[a].add(line[j])
                }
            }
        }
    }
    /*
    for(i in 1 until n+1){
        println(graph[i])
    }
    println()
    for(i in 1 until n+1){
        println(dist[i])
    }
*/
    bfs(1,0)
    visit = BooleanArray(n+1){false}
    //println(point)
    bfs(point,0)
    bw.write("$ans")
    bw.flush()
    bw.close()
}
 
fun bfs(v:Int,d:Int){
    var index = 0
    visit[v]=true
    for(i in graph[v]){
        if(!visit[i]){
           // println(dist[v][index])
            var distant =d+dist[v][index]
            if(ans<distant) {
                point=i
                ans = distant
            }
            bfs(i,distant)
        }
        index++
    }
 
}