요즘 알고리즘 공부가 너무 뜸했던 이유...
주 5일 한달반 토익 학원을 다니고 있습니다ㅠㅠ 요즘 영어 실력이 늘어서 가끔 미디엄 글 시간날때 읽으면 잘 읽히는건 좋은데,, 절대적으로 시간이 부족해서 미디엄을 잘 못읽고 다른 분야 공부를 아예 못하고 있는게 좀 아쉽다(토익 공부하고 진행 중인 플젝 하면 하루가 다 가는...).
그래도 오랜만에 백준 하루 한 문제 챌린지를 다시 시작하려한다. (블로그에는 내가 처음 접하는 유형이거나 의미있다고 생각되는 문제들만 올릴 예정이다)
원래는 2월안에 골1 달아놓으려고 했는데 아마 골2 중간까지 밖에 못갈것 같다. 그래도 꾸준히 열심히..

문제 설명

우선, 이 문제는 트리를 알아야 한다. 트리란? 그래프 중에서도 특이한 성질을 가진 그래프임.
트리는 사이클이 없고, 방향도 없다. 이말이 무슨말인지 잘 생각해보자.
사이클이 없다는 말은 어떤 임의 a노드에서 임의 b노드까지 가는 경로가 오직 한 개라는 것을 말한다. 만약 이 경로가 두 가지라면 그 중간 분기점에서 헤어졌다가 다시 만나는 지점이 존재할 것이므로, 그 사이에 사이클이 존재하게 된다.
또한, 이런 특징 떄문에 n개의 노드가 있는 트리는 정확히 n-1개의 간선을 갖게된다.

그렇다면, 트리의 지름은 무엇일까? 임의 두 노드 사이 거리 중 가장 긴 것을 말한다.
이 트리에서는 9번 노드에서 12번 노드로 가는 경로가 트리의 지름이 된다.

문제는 다음과 같다.
트리 내 정점의 갯수와 간선의 정보가 모두 주어졌을 때, 트리 내에서 트리의 지름을 찾고 그 길이를 출력하면 된다.

문제 접근

사실 이 유형은 예전에 다른 문제를 풀다가 만난 적이 있다.
우선, 정점간 거리를 구해야하는데, 플로이드 워샬은 v가 1000을 넘기면 쓰기 어렵다. 그렇다면 다익스트라로 해결해야할 확률이 높은데, 잘 생각해보면 단 두 번의 다익스트라로 구할 수 있다.
자, 우리가 a노드에서 시작해서 다익스트라를 적용했다고 해보자. 그러면, 그 중 가장 긴 값까지의 경로는 반드시, 트리의 지름을 만드는 두 노드 중 한개일 수 밖에 없다.
-> 처음에는 안와닿을 수 있다. 그렇다면 이 그림을 보자. 트리의 지름으로 만들어진 원 안에 다른 모든 점들이 들어가야 한다는 사실은 좀만 고민해보면 당연하다는 것을 알 수 있다.

그렇다면, 생각해보자.
트리의 지름이 아닌 한 점에서 가장 먼 점이 만약 트리의 지름을 만드는 두 노드 중 한 개가 아니라면, 그 점은 트리의 지름이 만드는 원 안에 들어갈 수 없다. 즉, 모순이 발생한다는 것이다. 이것에 대한 상세한 증명은 다른 블로그글들에서 귀류법을 써서 잘 소개하고 있다.

그렇다면, 우리는 아무 정점이나 하나를 시작점으로 잡고 다익스트라로 가장 먼 점을 구하고, 구한 그 점을 시작으로 하는 다익스트라를 수행해서 트리 지름의 나머지 끝 점을 찾으면 된다.

코드

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

public class Main {
    static ArrayList<Node>[] tree;
    static int N;
    static final int INF = 10_0000_0000;

    static class Node {
        final int end;
        final int cost;

        Node(int end, int cost) {
            this.end = end;
            this.cost = cost;
        }
    }

    public static void main(String[] args) throws IOException {        // 현재 시간을 가져오기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        tree = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            tree[i] = new ArrayList<>();
        }

        for (int i = 0; i < N - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            tree[s].add(new Node(e, c));
            tree[e].add(new Node(s, c));
        }

        if (N == 1) {
            System.out.println(0);
            return;
        }

        List<Integer> results = dijkstra(1);
        int result = dijkstra(results.get(1)).get(0);
        System.out.println(result);
    }

    static List<Integer> dijkstra(int s) {
        int max = 0;
        int nodeNumber = s;
        int[] table = new int[N + 1];
        Arrays.fill(table, INF);
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> {
            return o1.cost - o2.cost;
        });
        pq.add(new Node(s, 0));
        table[s] = 0;

        while (!pq.isEmpty()) {
            Node curN = pq.poll();
            for (Node nextN : tree[curN.end]) {
                if (table[nextN.end] > table[curN.end] + nextN.cost) {
                    table[nextN.end] = table[curN.end] + nextN.cost;
                    pq.add(new Node(nextN.end, table[nextN.end]));
                }
            }
        }

        for (int i = 1; i < N + 1; i++) {
            if (i == s) continue;
            if (max < table[i]) {
                max = table[i];
                nodeNumber = i;
            }
        }
        return List.of(max, nodeNumber);
    }
}