BOJ_1167 트리의 지름 Gold.2

문제 내용

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

INPUT

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

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

OUTPUT

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

---

제가 생각한 문제의 의도는 결과적으로 트리의 지름, 즉 트리의 특성에 대해 정확하게 이해하고 있는지가 핵심이라고 생각합니다.

트리의 특징
1. 싸이클이 존재하지 않음
2. 노드가 N개인 트리는 항상 N - 1 개의 간선을 가짐
3. 임의의 두 노드 간의 경로는 유일하다. 즉 두 개의 노드 사이에 반드시 1개의 경로만을 가짐

그렇다면 지름을 구하기 위해서,

어떤 임의의 정점에서 출발하여 가장 거리가 먼 정점까지의 거리를 구할때, 경로가 겹치는 부분이 필연적으로 존재함

이 말을 이해해야 합니다. 왜냐하면, 트리에서는 싸이클이 존재하지 않기 때문에 겹치는 경로가 존재할 수 밖에 없습니다.

1. 즉, 임의의 정점에서 거리가 가장 먼 임의의 정점까지의 거리를 구하기
2. 해당 거리가 가장 먼 정점에서 가장 거리가 먼 임의의 정점까지 거리를 구하기

이 둘의 거리를 비교하여 가장 먼 거리가 트리에서 지름이 됩니다.

간선의 개수만큼의 시간복잡도로 끝낼 수 있습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    static class Node {
        int index;
        Map<Integer, Integer> cost = new HashMap<>();
        List<Node> adjacent = new ArrayList<>();

        public Node(int index) {
            this.index = index;
        }
    }

    private static List<Node> graph = new ArrayList<>();
    private static int tempIndex;
    private static long answer = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input;
        int V = Integer.parseInt(br.readLine());

        for (int i = 0; i <= V; i++) {
            graph.add(new Node(i));
        }


        for (int i = 0; i < V; i++) {
            input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            int x = input[0];

            for (int j = 1; j < input.length - 1; j = j + 2) {
                int y = input[j];
                Node nodeA = graph.get(x);
                Node nodeB = graph.get(y);

                if (nodeA.cost.getOrDefault(nodeB.index, 0) == 0 ||
                        nodeB.cost.getOrDefault(nodeA.index, 0) == 0) {
                    nodeA.cost.put(nodeB.index, input[j + 1]);
                    nodeB.cost.put(nodeA.index, input[j + 1]);

                    nodeA.adjacent.add(nodeB);
                    nodeB.adjacent.add(nodeA);
                }
            }
        }

        System.out.println(getMaxDistance());
    }

    private static long getMaxDistance() {
        long[] costs = new long[graph.size()];

        boolean[] visited = new boolean[graph.size()];

        dfs(1, visited, 0);

        visited = new boolean[graph.size()];

        dfs(tempIndex, visited, 0);

        return answer;
    }

    private static void dfs(int index, boolean[] visited, long cost) {
        visited[index] = true;

        if (cost > answer) {
            answer = cost;
            tempIndex = index;
        }

        Node node = graph.get(index);

        for (Node next : node.adjacent) {
            if(visited[next.index]) continue;
            dfs(next.index, visited, cost + node.cost.get(next.index));
        }
    }
}