[Java] 백준 1167 트리의 지름 풀이

✅문제

✅문제 풀이 

트리의 지름 즉 트리에서 가장 먼 정점 사이의 거리를 구하는 문제이다.

가장 쉬운 방법으로는 브루트포스 처럼 모든 정점에서의 거리를 구해서 그 거리중에서 최대 값을 구해도 답은 나오겠지만 아쉽게도 이 문제는 모든 정점에서의 거리를 하나하나 구하면 시간초과로 실패한다.

 

그렇다면 어떻게 해야할까. 일단 트리에 특성에 대해서 알아야한다. 일단 트리는 모든 정점은 사이클이 존재하지 않아서 한 정점에서 다른 정점으로 가는길은 유일하다는 특성을 알고있어야한다.

위 그림은 예제에서 나오는 트리를 그려본건데, 2 -> 4, 4 -> 3으로 가는 방법은 유일하고 순환이 있는 순간 트리라고 부르지 않는다.

따라서 무조건적으로 가장 먼 정점 사이의 거리는 무조건 하나 밖에 없다.

여기서도 1 -> 5로 가는 것이 가장 먼 정점인 것을 알 수 있다.

또한가지 알 수 있는 것이 어느 정점에서든 가장 먼 정점을 구하면 1,5둘중 하나라는 것을 알 수 있다.

 

이런 특성을 이용해 아무 정점에서 가장 먼 정점 bfs로 구하고 (트리의 지름의 한 끝점을 구하는것)

그 정점에서 또 가장 먼 정점까지의 거리를 bfs로 구하면 (트리의 지름의 또하나의 끝점을 구하는것)

이 트리에서 가장 먼 거리를 구할 수 있는 것을 알 수 있다.

 

어느 정점에서 가장 먼 정점을 구하면 트리의 지름의 한 끝점이 구해지는 이유는 밑에 이유인데 머리로는 알겠는데 항상 그럴수있는 감이 안잡혀서 좀 어려운것같다

1. 임의의 정점 A에서 가장 먼 정점 U:

• 정점 A에서 가장 먼 정점 U를 찾는다는 것은, U가 A로부터의 최대 거리에 있는 정점임을 의미.
• 따라서, 경로  P(A, U) 는 트리에서 가장 긴 경로 중 하나임

2. 반례를 통한 증명:

• 만약 U가 지름의 한 끝점이 아니라면, U에서 더 먼 정점이 존재.
• 그러나, BFS/DFS를 통해 U를 찾았기 때문에, U는 A로부터 가장 먼 정점.
• 따라서, U가 지름의 한 끝점이 됨

3. 지름의 대칭성:

• 트리의 지름은 항상 두 끝점임.
• 첫 번째 탐색에서 찾은 U는 그 끝점 중 하나임.

✅Code

package classthree;

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

public class Beak1167 {
    public static class Node {
        int e;
        int cost;
        public Node(int e, int cost) {
            this.e = e;
            this.cost = cost;
        }
    }
    public static void doBfs(int n, List<Integer> checks, List<List<Node>> arrays){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);
        checks.set(n, 0);

        while (!queue.isEmpty()) {
            int dn = queue.remove();

            for (int i = 0; i < arrays.get(dn).size(); i++) {
                Node node = arrays.get(dn).get(i);
                if(checks.get(node.e) == -1) {
                    queue.add(node.e);
                    checks.set(node.e, checks.get(dn) + node.cost);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<List<Node>> arrays = new ArrayList<>();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            arrays.add(new ArrayList<>());
        }

        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            while (true) {
                int to = Integer.parseInt(st.nextToken());
                if (to == -1) {
                    break;
                }
                int cost = Integer.parseInt(st.nextToken());
                arrays.get(from - 1).add(new Node(to - 1, cost));
            }
        }

        List<Integer> checks = new ArrayList<>(Collections.nCopies(t, -1));
        doBfs(0, checks, arrays);

        int maxIndex = 0;
        int maxVal = Integer.MIN_VALUE;
        for (int i = 0; i < checks.size(); i++) {
            if (checks.get(i) > maxVal) {
                maxIndex = i;
                maxVal = checks.get(i);
            }
        }

        checks = new ArrayList<>(Collections.nCopies(t, -1));
        doBfs(maxIndex, checks, arrays);

        maxVal = Integer.MIN_VALUE;
        for (int i = 0; i < checks.size(); i++) {
            if (checks.get(i) > maxVal) {
                maxVal = checks.get(i);
            }
        }

        System.out.println(maxVal);
    }
}