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

백준 1167 - 트리의 지름

이 문제는 아무리 생각해도 어떻게 풀어야할지 감이 안 와서 검색해보니, 트리의 성질과 관련한 공식에 대한 이해가 필요한 문제였다.

루트에서 가장 먼 정점 A를 구하고, A에서 가장 먼 정점 B를 구하면(참고로 B가 루트 노드일 수도 있다) A와 B의 거리가 트리의 지름이라는 것이었다.

이걸 처음 봤을 때는 오... 그렇구나.. 하면서도 수학적으로 증명이 된 건지 궁금했는데 다행히 증명 과정을 잘 적어놓은 블로그들도 많이 있었다. 물론...(^^) 증명들을 읽는다고 바로 이해가 가지는 않았는데, 개인적으로는 아래 블로그 설명이 가장 명확히 납득시켜 주었던 것 같다.
https://johoonday.tistory.com/217

이제 증명에 대한 이해까지 끝냈으면 문제를 풀 차례! 공식을 생각해내는 게 어려워서 그렇지 풀이 자체는 어렵지 않았다.
dfs(혹은 bfs)를 2번 수행해서 루트에서 가장 먼 노드와 그 노드에서 가장 먼 노드와의 거리를 구하면 된다.

아래는 전체 소스코드이다.

// 1167 - 트리의 지름
public class Main {
    static List<List<int[]>> list; // 노드의 번호와 간선의 거리 둘 다 저장해야하므로 int[] 

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        list = new ArrayList<>();
        for (int i = 0; i < N + 1; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int node = Integer.parseInt(st.nextToken());
            int n;
            int distance;
            while (true) {
                n = Integer.parseInt(st.nextToken());
                if (n == -1) {
                    break;
                }
                distance = Integer.parseInt(st.nextToken());
                list.get(node).add(new int[]{n, distance});
            }
        }
        br.close();

        boolean[] visited = new boolean[list.size()];
        visited[1] = true;
        // 루트 노드에 대한 dfs를 수행하고 가장 먼 거리와 노드 번호를 구한다.
        int[] fromRoot = dfs(1, visited, 0);
        visited = new boolean[list.size()];
        visited[fromRoot[1]] = true;
        // 가장 먼 노드에서부터 다시 dfs를 수행
        int[] farthest = dfs(fromRoot[1], visited, 0);

        bw.write(farthest[0] + "");
        bw.flush();
        bw.close();
    }

    static int[] dfs(int index, boolean[] visited, int distance) {
        int maxDistance = distance;
        int farthestNode = index;

        for (int[] node : list.get(index)) {
            if (!visited[node[0]]) {
                visited[node[0]] = true;
                int[] disAndNode = dfs(node[0], visited, distance + node[1]);
                if (disAndNode[0] > maxDistance) {
                    maxDistance = disAndNode[0];
                    farthestNode = disAndNode[1];
                }
            }
        }
        return new int[]{maxDistance, farthestNode};
    }
}