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

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

문제

• 트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

• 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

• 입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.

• 트리의 노드는 1부터 n까지 번호가 매겨져 있다.

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

public class Main {

    private static class Node {

        int num;    // 노드 번호
        int weight; // 가중치
        Node next;  // 다음 형제

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

    }

    private static Node[] adjList;
    private static int result, index;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(reader.readLine()); // 노드의 개수
        adjList = new Node[N + 1]; // 1-base index

        for (int i = 0; i < N - 1; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int from = Integer.parseInt(tokenizer.nextToken());
            int to = Integer.parseInt(tokenizer.nextToken());
            int weight = Integer.parseInt(tokenizer.nextToken());

            // 무향 그래프
            adjList[from] = new Node(to, weight, adjList[from]);
            adjList[to] = new Node(from, weight, adjList[to]);
        }

        int next = dfs(new boolean[N + 1], 1, 0);
        dfs(new boolean[N + 1], next, 0);

        System.out.println(result);
    }

    private static int dfs(boolean[] visited, int start, int sum) {
        visited[start] = true;

        for (Node node = adjList[start]; node != null; node = node.next) {
            if (!visited[node.num]) {
                dfs(visited, node.num, sum + node.weight);
            }
        }

        if (result < sum) {
            result = sum;
            index = start;
        }

        return index;
    }

}

• 일전에 풀었던 트리의 지름 문제와 같은 문제라고 봐도 무방하다. 이 문제는 가중치가 있다는 것이 차이점이다.