[백준] 1967번 : 트리의 지름 - JAVA [자바]

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

한 정점에서 가장 먼 노드까지의 거리 중 최대 값을 찾는 문제이다.

dfs 알고리즘을 이용해서 풀었다.

모든 노드마다 돌면서 찾으면 시간 초과가 발생한다.

1. 이 그래프는 1이 루트 노드이다.
2. 루트 노드 1을 기준으로 가장 먼 노드를 찾는다.
3. 찾은 노드에서 부터 가장 먼 거리의 노드를 찾는다.
4. 답을 출력한다.

public class bj1967 {

    public static int N, MAX = 0;
    public static int farFrom1 = 1;
    public static boolean[] visited;
    public static StringBuilder sb = new StringBuilder();
    public static ArrayList<ArrayList<int[]>> edgeList;

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

        N = Integer.parseInt(br.readLine());
        edgeList = new ArrayList<>();

        for (int i = 0; i <= N; i++) {
            edgeList.add(new ArrayList<>());
        }

        for (int n = 0; n < N - 1; n++) {
            String line = br.readLine();
            String[] split = line.split(" ");
            int from = Integer.parseInt(split[0]);
            int to = Integer.parseInt(split[1]);
            int length = Integer.parseInt(split[2]);
            edgeList.get(from).add(new int[]{to, length});
            edgeList.get(to).add(new int[]{from, length});
        }

        // 1 에서 가장 먼 노드를 찾는다.
        visited = new boolean[N + 1];
        dfs(1, 0);

        // 1에서 가장 먼 노드에서 시작하여 가장 먼 다른 노드를 찾는다.
        visited = new boolean[N + 1];
        dfs(farFrom1, 0);

        bw.write(MAX + "");

        bw.flush();
        bw.close();
        br.close();
    }

    public static void dfs(int start, int sum) {
        visited[start] = true;
        if (sum > MAX) {
            MAX = sum;
            farFrom1 = start;
        }

        for (int[] arr : edgeList.get(start)) {
            int to = arr[0];
            int length = arr[1];
            if (!visited[to]) {
                dfs(to, sum + length);
            }
        }
    }
}