백준 1967번
https://www.acmicpc.net/problem/1967

문제

---

생각하기

---

• 트리 문제인 줄 알고 풀려고 했는데, 다익스트라로 풀어지는 문제였다.

  • 사실상 그냥 양방향 그래프 문제

• 다익스트라의 최소 거리 구하기를 반대 개념으로 최대거리로 갱신해서 찾으면 답을 구할 수 있다.
  

동작

코드

---

Kotlin

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private lateinit var adjList: MutableList<MutableList<Node>>
private lateinit var isVisited: BooleanArray
private lateinit var dist: IntArray

data class Node(var num: Int = 0, var weight: Int = 0)

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    val sb = StringBuilder()
    
    input()

    // 루트에서 시작해서 가장 먼 노드를 찾기
    var ans = dijkstra(1)
    ans = dijkstra(dist.indexOf(ans))

    sb.append(ans)
    bw.write(sb.toString())
    bw.close()
} // End of main

private fun dijkstra(startNodeNum: Int): Int {
    val comp = Comparator<Node> { o1, o2 -> o1.weight - o2.weight }
    val que = PriorityQueue(comp)
    isVisited = BooleanArray(N + 1)
    dist = IntArray(N + 1) { -1 }

    dist[startNodeNum] = 0
    que.offer(Node(startNodeNum, 0))

    for (i in generateSequence { 0 }) {
        if (que.isEmpty()) break
        val pollNode = que.poll()

        if (isVisited[pollNode.num]) continue
        isVisited[pollNode.num] = true

        adjList[pollNode.num].forEach { nextNode ->

            // 다익스트라의 개념을 적용하되 가장짧은 거리로 최신화 하는 것이 아닌, 가장 먼 거리로 최신화를 함.
            if (!isVisited[nextNode.num] && dist[nextNode.num] < nextNode.weight + dist[pollNode.num]) {
                dist[nextNode.num] = nextNode.weight + dist[pollNode.num]
                que.offer(Node(nextNode.num, dist[nextNode.num]))
            }
        }
    }

    return dist.max()
} // End of dijkstra

fun input() {
    N = br.readLine().toInt()

    adjList = ArrayList()
    repeat(N + 1) {
        adjList.add(ArrayList())
    }

    repeat(N - 1) {
        val st = StringTokenizer(br.readLine())
        val parentNode = st.nextToken().toInt()
        val childNode = st.nextToken().toInt()
        val weight = st.nextToken().toInt()

        adjList[parentNode].add(Node(childNode, weight))
        adjList[childNode].add(Node(parentNode, weight))
    }
} // End of input