[Java] 백준 1167번 트리의 지름

처음에는 가장 먼 두 정점을 찾기 위해 Brute force를 생각했는데

아무리 생각해도 복잡도가 미친듯이 날뛸것같아서 결국 다른 글을 참고했다...

 

트리의 어떤 정점에서 가장 먼 정점을 찾으면

그 정점은 항상 트리의 지름의 양끝점 중 하나가 된다더라... 공부해야지

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

public class g3_1167 {
    static List<HashMap<Integer, Integer>> table = new ArrayList<>();
    static boolean[] check;
    static int far = -1;
    static int disMax = -1;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int V = Integer.parseInt(br.readLine());
        
        for (int i = 0; i < V + 1; i++){
            table.add(new HashMap<Integer, Integer>());
        }

        for (int i = 0; i < V; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int e = Integer.parseInt(st.nextToken());
            while (true){
                int next = Integer.parseInt(st.nextToken());
                if (next == -1) break;
                table.get(e).put(next, Integer.parseInt(st.nextToken()));
            }
        }

        check = new boolean[V + 1];
        find(1, 0);
        
        check = new boolean[V + 1];
        find(far, 0);
        
        bw.write(String.valueOf(disMax));
        bw.flush();
        bw.close();
    }

    public static void find(int now, int dis){
        if (dis > disMax){
            far = now;
            disMax = dis;
        }

        check[now] = true;
        for (Integer i : table.get(now).keySet()){
            if (!check[i]){
                find(i, dis + table.get(now).get(i));
            }
        }
    }
}