백준 - 트리의 지름(java)

백준에 트리의 지름이 2가지가 있는 데 어려운 난이도의 풀이로 쉬운 것도 풀 수 있다.

import java.io.*;
import java.util.*;

class Node {
    int to, weight;

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

public class Main {
    static ArrayList<Node>[] tree;
    static boolean[] visited;
    static int maxDistance;
    static int maxNode;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());

        tree = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) {
            tree[i] = new ArrayList<>();
        }

        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            tree[parent].add(new Node(child, weight));
            tree[child].add(new Node(parent, weight)); 
        }

        visited = new boolean[N + 1];
        maxDistance = 0;
        dfs(1, 0);
        visited = new boolean[N + 1];
        dfs(maxNode, 0);

        System.out.println(maxDistance);
    }

    public static void dfs(int currentNode, int distance) {
        visited[currentNode] = true;
        if (distance > maxDistance) {
            maxDistance = distance;
            maxNode = currentNode;
        }
        for (Node node : tree[currentNode]) {
            if (!visited[node.to]) {
                dfs(node.to, distance + node.weight);
            }
        }
    }
}

1. 양방향 그래프로 부모와 자식관계를 맺어준다.
2. dfs를 이용해서 거리를 계산해주는 매서드를 만든다.
3. 임의의 점에서 dfs를 해줘서 트리의 끝점에 있는 아무점을 찾아준다. 양방향 그래프라 임의의 점에서 해줘도 결국엔 끝점으로 간다.
4. 양방향 그래프와 visited[]로 결국엔 모든 점을 탐색한다. 끝점에서 시작하면 결국엔 모든 끝점을 둘러보고 거리를 계산하기 때문에 지름이 되는 끝점들을 탐색할 수 있다.