1. 문제

📌 문제 보러 가기!

2. 접근법

처음에는 DFS를 각 정점에서 모두 돌려 완전 탐색을 시도했으나...
V의 범위가 100,000 까지이니 O(N^2)의 시간복잡도를 가지게 되어 시간 초과가 났다

고민을 하다 구글링 한 결과 해결법을 찾게 되었다

핵심 아이디어는 "임의의 노드에서 가장 긴 경로로 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나다"

즉, 아무 노드에서 가장 먼 경로에 있는 노드를 찾은 후, 해당 노드에서 가장 먼 거리를 찾으면 그것이 트리의 지름이 되는 것이다~
처음에는 이해가 잘 안 됐지만 오래 고민을 해 보니 당연한 해답이었다!

3. 코드

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

public class BaekJoon1167 {
    static ArrayList<int[]>[] arr;
    static boolean[] visited;
    static int node;
    static int maxValue = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = new ArrayList[N + 1];
        visited = new boolean[N + 1];
        StringTokenizer st;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            arr[t] = new ArrayList<int[]>();

            while (st.hasMoreTokens()) {
                int k = Integer.parseInt(st.nextToken());

                if (k == -1) {
                    break;
                }

                int v = Integer.parseInt(st.nextToken());

                arr[t].add(new int[]{k, v});
            }
        }

        DFS(1, 0);
        maxValue = 0;
        visited = new boolean[N + 1];
        DFS(node, maxValue);
        System.out.println(maxValue);

    }

    static void DFS(int n, int cnt) {
        visited[n] = true;

        if (cnt > maxValue) {
            node = n;
            maxValue = cnt;
        }

        for (int[] num : arr[n]) {
            if (!visited[num[0]]) {
                DFS(num[0], cnt + num[1]);
            }
        }
    }
}