[백준 1967번] 트리의 지름

문제 링크: 1967번 트리의 지름

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

 

풀이 자체는 상당히 직관적인데, 전제에 대한 '직관'만 있는 것에 대한 증명을 누군가 잘 해주셨다(다만 댓글을 꼭 읽어야 한다).

https://blog.myungwoo.kr/112

 

처음에 하나의 정점 u로부터 가장 먼 정점 v를 찾을 건데, 일단 루트를 u로 해서 v를 찾는다.

그 다음, v로부터 가장 먼 정점을 찾는다. 그리고 두 정점 간의 거리를 출력한다.

 

이렇게 DFS 2번을 사용하는 것이 마치 국룰과 같은 풀이이다.

 

하나는 아직은 잘 이해되지 않는 DP 풀이이다. 트리 DP는 앞으로도 계속 사용될 것이기에 꼭 살펴보아야 한다.

https://suuntree.tistory.com/172

 

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

class Node {
    int n;
    int d;

    public Node(int n, int d) {
        this.n = n;
        this.d = d;
    }
}

public class Main {
    static boolean[] visit;
    static List<Node>[] tree;
    static int[] dist;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        tree = new ArrayList[n+1]; for (int i = 1; i < n+1; i++) tree[i] = new ArrayList<Node>();

        for (int i = 0; i < n-1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int p = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            tree[p].add(new Node(c, w));
            tree[c].add(new Node(p, w));
        }
        
        // root에서 가장 먼 노드를 구하자
        visit = new boolean[n+1];
        dist = new int[n+1];
        dist[1] = 0;
        dfs(1, 0);

        int max = -1;
        int maxNode = -1;
        for (int i = 1; i <= n; i++) {
            if (dist[i] > max) {
                max = dist[i];
                maxNode = i;
            }
        }

        for (int i = 1; i <= n; i++) dist[i] = 0;
        for (int i = 1; i <= n; i++) visit[i] = false;
        dfs(maxNode, 0);

        for (int i = 1; i <= n; i++) if (dist[i] > max) max = dist[i];
        System.out.println(max);
    }

    static void dfs(int u, int d) {
        if (visit[u]) return;
        visit[u] = true;
        dist[u] = d;

        for (Node v : tree[u]) {
            dfs(v.n, d + v.d);
        }
    }
}