[백준] 12912번 - 트리 수정 (Gold 1)

문제 링크

백준 12912번 - 트리 수정 (Gold 1)

문제 설명

트리에서 간선 하나를 제거하고 제거한 간선의 가중치와 같은 가중치를 가지는 간선을 하나 추가하여 새로운 트리를 만드려고 한다. 가능한 새로운 트리의 지름의 최댓값을 구하시오.

정답 코드 및 설명

먼저, 특정한 간선 하나를 제거하고, 제거한 간선의 가중치와 같은 가중치를 가지는 간선을 하나 추가했을 때 만들어지는 새로운 트리의 지름으로 가능한 최댓값을 구하자.
트리에서 간선을 하나 제거하면 연결 요소가 두 개인 그래프가 된다.
처음 트리에 사이클이 없으므로, 간선을 제거해도 사이클이 없다. 따라서 각각의 연결 요소는 트리가 되고, 지름을 구할 수 있다.
이제 간선을 하나 추가해서 만든 트리의 지름으로 가능한 최댓값은 각 트리의 지름 + 추가될 간선의 가중치이다.

트리 A에서 가장 멀리 떨어진 두 노드가 a1, a2이고, 트리 B에서 가장 멀리 떨어진 두 노드가 b1, b2라고 하자.
트리 A의 노드 a3와 트리 B의 노드 b3를 가중치 w인 간선으로 연결했다고 하자. 트리 A 안의 노드 a와 트리 B 안의 노드 b에 대해, a와 b 사이의 거리는 a와 a3 사이의 거리 + a3와 b3 사이의 거리 + b3와 b 사이의 거리를 넘을 수 없다. a와 a3 사이의 거리는 트리 A의 지름 이하이고, b3와 b 사이의 거리는 트리 B의 지름 이하이며, a3와 b3 사이의 거리는 w이다.
따라서 전체 트리의 지름은 항상 트리 A의 지름 + 트리 B의 지름 + w 이하이다.
전체 트리의 지름 = 트리 A의 지름 + 트리 B의 지름 + w인 경우로는 a1 = a3, b1 = b3, a = a2, b = b2인 경우가 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ12912 {
    int n;
    ArrayList<Node>[] graph;
    Edge[] edges;
    long[] diameter;

    static class Edge {
        int from, to;
        long cost;

        Edge(int from, int to, long cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }

        public boolean equals(int from, int to) {
            return (from == this.from && to == this.to) || (from == this.to && to == this.from);
        }
    }

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        edges = new Edge[n - 1];
        graph = new ArrayList[n];
        for (int i = 0; i < n; i++)
            graph[i] = new ArrayList<>();
        diameter = new long[n];
        StringTokenizer st;
        int from, to, cost;
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            cost = Integer.parseInt(st.nextToken());
            graph[from].add(new Node(to, cost));
            graph[to].add(new Node(from, cost));
            edges[i] = new Edge(from, to, cost);
        }
    }

    int edgeNo;

    void maxDist(int start) {
        int size = graph[start].size();
        for (int i = 0; i < size; i++) {
            Node curr = graph[start].get(i);
            if (edges[edgeNo].equals(start, curr.node)) continue;
            if (diameter[curr.node] != -1) continue;
            diameter[curr.node] = diameter[start] + curr.cost;
            maxDist(curr.node);
        }
    }

    static class Node {
        int node;
        long cost;

        public Node(int node, long cost) {
            this.node = node;
            this.cost = cost;
        }
    }

    Node max(int start) {
        int index = 0;
        long max = -1;
        Arrays.fill(diameter, -1);
        diameter[start] = 0;
        maxDist(start);
        for (int i = 0; i < diameter.length; i++) {
            if (diameter[i] > max) {
                max = diameter[i];
                index = i;
            }
        }
        return new Node(index, max);
    }

    long diameter(int start) {
        int first = max(start).node;
        return max(first).cost;
    }

    long diameter() {
        return diameter(edges[edgeNo].from) + diameter(edges[edgeNo].to) + edges[edgeNo].cost;
    }

    void solution() throws IOException {
        input();
        long diameter = 0;
        for (edgeNo = 0; edgeNo < n - 1; edgeNo++) {
            diameter = Math.max(diameter, diameter());
        }
        System.out.println(diameter);
    }

    public static void main(String[] args) throws IOException {
        new BOJ12912().solution();
    }
}