[백준 1167] 트리의 지름(Java)

문제 링크 : https://www.acmicpc.net/problem/1167

이 문제는 bfs와 트리의 성질을 이용하여 풀 수 있습니다. 트리는 오직 하나의 부모만을 가지며 순환 사이클이 없기 때문에 임의의 노드에서 bfs를 이용하여 가장 먼 거리의 노드를 구했을 경우 그 노드는 트리의 지름을 구성하는 두 노드 중 하나가 됩니다. 따라서 임의의 점에서 bfs로 탐색하여 트리의 지름 노드 하나를 구한 후 그 노드에서 다시 bfs 탐색하여 가장 먼 거리가 곧 트리의 지름이 됩니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

class Main{
    static List<Node>[] graph;
    static boolean[] check;
    static int[] max;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        graph = new List[N+1];
        for(int i=1;i<=N;i++) graph[i] = new ArrayList<>();

        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            while(true){
                int v = Integer.parseInt(st.nextToken());
                if(v == -1) break;
                int d = Integer.parseInt(st.nextToken());

                graph[s].add(new Node(v,d,1));
                graph[v].add(new Node(s,d,1));
            }
        }

        max = new int[N+1];
        check = new boolean[N+1];
        int res = 0;
        res = Math.max(res, bfs(new Node(1,0,0)));

        int mx = 0;
        int idx = 0;
        for(int i=2;i<=N;i++){
            if(mx < max[i]){
                idx = i;
                mx = max[i];
            }
        }
        check = new boolean[N+1];
        res = Math.max(res, bfs(new Node(idx,0,0)));
        System.out.println(res);
    }

    static int bfs(Node start){
        check[start.val] = true;
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(start);

        int res = 0;
        while(!queue.isEmpty()){
            Node curr = queue.poll();
            res = Math.max(res, curr.cnt);
            max[curr.val] = Math.max(max[curr.val],curr.cnt);

            for(Node next : graph[curr.val]){
                if(!check[next.val]){
                    check[next.val] = true;
                    queue.add(new Node(next.val, next.dis, curr.cnt+next.dis));
                }
            }
        }
        return res;
    }

    static class Node{
        int val;
        int dis;
        int cnt;

        Node(int val, int dis, int cnt){
            this.val = val;
            this.dis = dis;
            this.cnt = cnt;
        }
    }
}