Today I Learned

오늘은 코틀린 코테 연습!

CT_트리의 지름

백준 1167번 https://www.acmicpc.net/problem/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

풀이 과정

• 트리를 입력으로 받아서 DFS를 이용해 트리의 지름을 찾았다. 임의의 정점에서 가장 먼 정점을 찾은 뒤 그 정덤에서 가장 먼 정점을 찾아 트리의 지름을 구했다.

1. BufferedReader를 이용해 입력을 받는다. 정점의 개수 V를 받고, 트리를 표현할 2차원 ArrayList 배열 tree를 초기화한다. 방문 여부를 저장할 visited 배열도 초기화 한다.

2. 정점의 개수만큼 reapeat으로 반복하면서 각 정점과 연결된 노드들을 입력으로 받는다. 정점, 연결된 정점, 가중치의 형식으로 입력을 받아 트리에 추가한다.

3. 트리를 찾기 위해 DFS 함수를 정의한다. 현재 노드를 방문 표시하고, 현재까지의 거리를 저장한다. 인접한 노드들을 확인하면서 방문하지 않은 노드를 재귀적으로 방문한다.

4. 1번노드에서 DFS를 시작해 가장 먼 노드를 찾고, visited를 초기화 한 뒤 다시 가장 먼 노드에서 DFS를 시작해 거기서 가장 먼 노드를 찾아 트리의 지름을 구하면 완료!

Kotlin 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

data class Node(val vertex: Int, val weight: Int)

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val V = br.readLine().toInt()

    val tree = Array(V + 1) { ArrayList<Node>() }
    val visited = BooleanArray(V + 1)

    repeat(V) {
        val st = StringTokenizer(br.readLine())
        val vertex = st.nextToken().toInt()

        while (true) {
            val v = st.nextToken().toInt()
            if (v == -1) break
            val weight = st.nextToken().toInt()
            tree[vertex].add(Node(v, weight))
        }
    }

    var maxDistance = 0
    var farthestNode = 0

    fun dfs(node: Int, distance: Int) {
        visited[node] = true

        if (distance > maxDistance) {
            maxDistance = distance
            farthestNode = node
        }

        for (adjacent in tree[node]) {
            if (!visited[adjacent.vertex]) {
                dfs(adjacent.vertex, distance + adjacent.weight)
            }
        }
    }

    dfs(1, 0)
    visited.fill(false)
    dfs(farthestNode, 0)

    println(maxDistance)
}