백준 1167 트리의 지름 Java [트리, DFS]

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

 

한 정점에서 가장 먼 거리의 노드 구하고 구한 노드로부터 가장 먼 거리를 리턴하면 된다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;


public class Main {
    static int[] vtd;
    static int V;
    static HashMap<Integer, ArrayList<int[]>> nodes;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        V = Integer.parseInt(br.readLine());
        nodes = new HashMap<>();
        vtd = new int[V+1];
        Arrays.fill(vtd, -1);
        for(int v = 0; v < V; v++) {
            int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            ArrayList<int[]> value = new ArrayList<>();
            for (int i = 1; i < arr.length-1; i+=2) {
                value.add(new int[]{arr[i], arr[i+1]});
            }
            nodes.put(arr[0], value);
        }
        vtd[1] = 0;
        dfs(1);
        dfs(getmax()[0]);
        System.out.println(getmax()[1]);
    }
    static void dfs(int node) {
        for (int[] arr : nodes.get(node)) {
            if (vtd[arr[0]] == -1) {
                vtd[arr[0]] = vtd[node] + arr[1];
                dfs(arr[0]);
            }
        }
    }
    static int[] getmax() {
        int index = 1, len = vtd[index];
        for(int i = 2; i <= V; i++) {
            if (vtd[i] > len) {
                index = i;
                len = vtd[i];
            }
        }
        Arrays.fill(vtd, -1);
        vtd[index] = 0;
        return new int[]{index, len};
    }
}