문제

풀이

V가 100,000개이므로 시간초과가 나지 않도록 풀어야 한다.
트리의 지름을 구하는 공식은 한 점에서 가장 먼 점을 구한 뒤
그 점에서 가장 먼 거리를 구하면 된다.

코드

static ArrayList<Edge>[] nodes;
인접리스트 nodes에는 Edge들이 들어간다.

static class Edge {
        int end;
        int distance;

        public Edge(int end, int distance) {
            this.end = end;
            this.distance = distance;
        }
    }

Edge 클래스
끝점과 거리를 멤버변수로 갖고 있다.

static class Node {
        int idx;
        int dis;

        public Node(int idx, int dis) {
            this.idx = idx;
            this.dis = dis;
        }
    }    

Node 클래스
index와 거리를 멤버변수로 갖고있다.

bfs(1)을 통해 1에서 가장 거리가 먼 노드를 찾고
bfs(maxNode)를 통해 가장 긴 거리를 찾는다.

전체코드

package baekjoon._1167;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static class Edge {
        int end;
        int distance;

        public Edge(int end, int distance) {
            this.end = end;
            this.distance = distance;
        }
    }

    static class Node {
        int idx;
        int dis;

        public Node(int idx, int dis) {
            this.idx = idx;
            this.dis = dis;
        }
    }
    static int V, maxNode, ans;
    static ArrayList<Edge>[] nodes;
    static boolean[] visited;

    public static void main(String[] args) {
        input();
        bfs(1);
        bfs(maxNode);
        System.out.println(ans);
    }

    public static void input() {
        FastReader fr = new FastReader();
        V = fr.nextInt();
        nodes = new ArrayList[V + 1];
        for (int i = 1; i <= V; i++) {
            nodes[i] = new ArrayList<>();
        }
        for (int i = 1; i <= V; i++) {
            int idx = fr.nextInt();
            while (true) {
                int vertex = fr.nextInt();
                if(vertex == -1) break;
                int distance = fr.nextInt();
                nodes[idx].add(new Edge(vertex, distance));
            }
        }
    }

    public static void bfs(int start) {
        visited = new boolean[V + 1];

        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(start, 0));
        visited[start] = true;

        int max = 0;

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (cur.dis > max) {
                max = cur.dis;
                maxNode = cur.idx;
            }

            for (Edge edge : nodes[cur.idx]) {
                if (!visited[edge.end]) {
                    visited[edge.end] = true;
                    queue.add(new Node(edge.end, cur.dis + edge.distance));
                }
            }
        }

        ans = Math.max(ans, max);
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader(){ br = new BufferedReader(new InputStreamReader(System.in));}

        String next(){
            while(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }

        Double nextDouble() { return Double.parseDouble(next()); }

        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            } catch(IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}

느낀점

Graph문제가 오랜만이어서 어떻게 풀어야할지 감이 안잡혔다.
Graph는 Edge클래스를 생성해야하고 인접리스트 혹은 인접배열으로 표현할 수 있다는 것을 기억하자