[백준] 19581. 두 번째 트리의 지름

트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다.

트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리는 두 번째 트리의 지름을 구하려고 한다.

 

두 번째 트리의 지름은 무엇이냐? 바로 두 번째로 가장 먼 두 정점 간의 거리를 의미한다. (두 번째 트리의 지름은 트리의 지름과 같을 수 있다.)

바로 두 번째 트리의 지름을 구해보자.

---

입력

첫 번째 줄에는 정점의 개수 N(3 ≤ N ≤ 100,000)이 들어온다.

둘째 줄부터 N번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수와 두 번째 정수는 간선과 연결된 정점 번호를 나타내고, 세 번째 정수는 간선의 가중치를 나타낸다. 간선의 가중치는 20,000 이하의 자연수이다.

출력

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

---

예제 입력

7
1 2 1
2 3 2
1 4 3
1 5 1
5 6 1
6 7 1

예제 출력

6

---

트리의 지름을 구하는 방법은(2022.07.19 - [PS/Java] - [백준] 1967. 트리의 지름)과 동일하다

두번째 트리의 지름을 구해야 하는데 임의의 정점으로부터 가장 먼 정점 A를 찾고

A로부터 가장 먼 정점 B를 찾아 트리의 지름을 구한다.

A로부터 B를 제외한 가장 먼 정점까지의 거리, B로부터 A를 제외한 가장 먼 정점까지의 거리를 구하고

두 값의 최대값을 구하면 두 번째 트리의 지름을 구할 수 있다. 제외하는 이유는 해당 값이 항상 첫 번째 가장 큰 트리의 지름이기 때문이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static int N, maxTo, maxW;
    public static int a, b, minA, minB;
    public static ArrayList<Node>[] adjList;
    public static boolean[] visited;
    public static class Node {
        int next;  // 누구랑 연결되어있는지
        int w;      // 가중치

        public Node (int next, int w) {
            this.next = next;
            this.w = w;
        }
    }
    
    public static void main(String[] args) throws Exception {
        N = Integer.parseInt(br.readLine());
        adjList = new ArrayList[N + 1];

        for(int i = 1; i <= N; i++) {
            adjList[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < N - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            adjList[from].add(new Node(to, weight));
            adjList[to].add(new Node(from, weight));
        }

        maxTo = 0;
        visited = new boolean[N + 1];
        maxW = Integer.MIN_VALUE;
        dfs(1, 0);  // 어디까지 제일 먼지 체크해서 값 기억
        // maxTo, maxW 구해짐 -> a
        a = maxTo;


        visited = new boolean[N + 1];
        maxW = Integer.MIN_VALUE;
        dfs(maxTo, 0);
        b = maxTo;


        visited = new boolean[N + 1];
        visited[b] = true;
        maxW = Integer.MIN_VALUE;
        dfs(a, 0);
        minA = maxW;

        visited = new boolean[N + 1];
        visited[a] = true;
        maxW = Integer.MIN_VALUE;
        dfs(b, 0);
        minB = maxW;

        bw.write(Math.max(minA, minB) + "");
        
        br.close();
        bw.flush();
        bw.close();
    }

    public static void dfs(int from, int dist) {
        if(visited[from]) {
            return;
        }
        if(maxW < dist) {
            maxTo = from;
            maxW = dist;
        }
        visited[from] = true;
        for(int i = 0; i < adjList[from].size(); i++) {
            Node nextNode = adjList[from].get(i);
            int next = nextNode.next;
            int w = nextNode.w;
            if(!visited[next]) {
                dfs(next, dist + w);
            }
        }
    }
}