[Baekjoon] 1167: 트리의 지름

문제

트리에서 두 점 사이의 거리가 가장 긴 길이를 트리의 지름이라 하는데 트리의 지름을 구하는 문제이다

 

풀이

내 풀이

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

public class Q1167 {

    private static List<List<int[]>> tree;
    private static boolean[] visited;
    private static int maxVertex;
    private static int max;

    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<>();
        for (int i = 0; i <= n; i++) {
            tree.add(new ArrayList<>());
        }
        visited = new boolean[n + 1];
        max = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int vertex1 = Integer.parseInt(st.nextToken());
            while (true) {
                int vertex2 = Integer.parseInt(st.nextToken());
                if (vertex2 == -1) {
                    break;
                }
                int weight = Integer.parseInt(st.nextToken());
                tree.get(vertex1).add(new int[]{vertex2, weight});
            }
        }

        visited[1] = true;
        search(1, 0);
        visited[1] = false;
        visited[maxVertex] = true;
        search(maxVertex, 0);

        System.out.println(max);
    }

    public static void search(int cur, int total) {
        if (total > max) {
            max = total;
            maxVertex = cur;
        }

        for (int[] next : tree.get(cur)) {
            if (!visited[next[0]]) {
                visited[next[0]] = true;
                search(next[0], total + next[1]);
                visited[next[0]] = false;
            }
        }
    }
}

풀이가 너무 오래걸려 힌트를 참고했다. 풀이 방법은 다음과 같다.

1. 임의의 정점(a)에서 가장 길이가 긴 정점(b)을 구한다.
2. 구한 정점(b)에서 거리가 가장 긴 정점(c)을 찾는다.
3. 2번에서 구한 정점 사이의 거리(b와 c 거리)가 트리의 지름이다.

따라서 모든 정점을 탐색할 필요없이 임의의 한 정점과, 그 정점에서 구한 정점, 총 2번 탐색하면 답을 구할 수 있다.

그럼 여기서 궁금해진다. 어떻게 이렇게 하면 답이 보장되는가?

 

증명

정점 b와 정점 c가 트리의 지름이 된다는 것은 트리 상에서 정점 a로부터 가장 멀리 떨어져 있는 정점 b는 항상 트리의 지름 끝부분에 있다는 의미이다.

따라서 귀류법을 통해 정점 b는 트리의 지름에 포함되지 않는다는 것이 모순임을 증명하면 된다.

 

먼저 정점 b가 트리의 지름에 포함되지 않는 경우들을 가정해보자. (그림이 정확히 그려지진 않지만 직관적으로 보자,,)

다음 경우들에서 임의의 정점 a로부터 가장 먼 정점 b가 있으며, 정점 x와 정점 y를 연결하는 경로가 트리의 지름이라고 하자.

 

1. 정점 a와 정점 x가 겹치는 경우

이 경우 d(a, b) == d(x, y)가 된다. 정점 a와 정점 x는 동일한 정점이기 때문에 정점 a로부터 가장 멀리있는 정점 b는 결국 트리의 지름인 y와 같은 거리에 있는 정점이 된다.

 

2. (a, b) 경로와 (x, y) 경로의 일부가 겹치는 경우

이 경우 정점 a로부터 가장 먼 정점인 b가 트리의 지름이 되려면 d(t, b)는 d(t, x)와 d(t, y)중 더 긴 경로의 길이와 같아야 한다. 때문에 (t, b)가 더 길게 된다면 y는 트리의 지름이 되지 못한다.

 

3. (a, b) 경로와 (x, y) 경로가 겹치지 않는 경우

 

이 경우 정점 a로부터 가장 먼 정점인 b가 트리의 지름이 되려면 d(t2, t1) + max(d(t1, x), d(t1, y))의 길이와 d(t2, b)의 길이가 같아야 한다. 하지만 이렇게 되면 (x, y)는 트리의 지름이라는 가정에 모순된다.

 

회고

트리의 지름을 2번에 구할 수 있다는 증명을 공부해보았다. 다음에 이 내용을 활용하는 문제가 나오면 까먹지말고 잘 활용해야겠다.