백준 - 1167번(트리의 지름)

문제 출처: https://www.acmicpc.net/problem/1167

문제

• 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    // 인접리스트를 만들기 위한 클래스
    private static class Node {

        int value;
        int weight;
        Node next;

        public Node(int value, int weight, Node next) {
            this.value = value;
            this.weight = weight;
            this.next = next;
        }

    }

    private static Node[] adjList;
    private static int tempLength, tempIndex;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int V = Integer.parseInt(reader.readLine()); // 정점의 개수

        adjList = new Node[V + 1]; // 1-base index
        int[] cnt = new int[V + 1];
        boolean[] target = new boolean[V + 1];
        for (int i = 0; i < V; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int value = Integer.parseInt(tokenizer.nextToken()); // 정점 번호
            int temp = 0;
            while ((temp = Integer.parseInt(tokenizer.nextToken())) != -1) { // -1이 아닐 때까지 진행
                adjList[value] = new Node(temp, Integer.parseInt(tokenizer.nextToken()), adjList[value]); // 정점 번호, 가중치, 다음 노드 주소
                cnt[value]++;
            }
        }

        dfs(1, new boolean[V + 1], 0);

        System.out.println(dfs(tempIndex, new boolean[V + 1], 0));
    }

    private static int dfs(int target, boolean[] visited, int length) {
        visited[target] = true;

        for (Node node = adjList[target]; node != null; node = node.next) {
            if (!visited[node.value]) { // 아직 방문하지 않은 노드의 경우
                dfs(node.value, visited, length + node.weight);
            }
        }

        // 갈 수 있는 끝까지 탐색한 경우
        if (tempLength < length) {
            tempLength = length;
            tempIndex = target;
        }

        return tempLength;
    }

}

• "트리의 지름"이라는 알고리즘이 있다는 것을 알게 해준 문제였다.
• 처음에는 모든 정점마다 DFS를 수행해서 가장 거리가 먼 두 노드를 찾는 방법을 썼으나 시간초과가 나왔다.
• 구글링하여 알고리즘을 참고하여 보니 처음에는 이해가 잘 되지 않았는데, 계속 생각해 본 결과 이해할 수 있었다.
• 먼저 처음에는 아무 점이나 하나 택하여 거리가 가장 먼 곳을 찾도록 DFS를 수행한다. 위의 코드에선 1번 정점을 시작 정점으로 택했다.
• 
• 사진 출처: https://koosaga.com/14
• 위 그림에서 보면, 1번에서 DFS를 수행하면 어찌됐든 가장 먼 정점을 찾을 것이다. (leaf 노드일 것이다.)
• 그러면 그 점은 트리의 지름을 구성하는 한 정점이 된다!
• 트리의 구조 상 DFS를 수행하면 모든 정점을 연결할 수 있다. 이러한 구조에서 어느 정점에서든 가장 먼 정점을 택하면 트리의 지름을 구성하는 두 정점 중 한 정점이 나오게 돼있다.
• 그렇다면 구한 하나의 정점에서 갈 수 있는 가장 먼 노드를 찾으면 이게 곧 지름이 된다!