문제

풀이

이해

트리의 지름은 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 문제이다.

정점의 개수가 주어지고 개수만큼 간선의 정보가 주어진다. 간선의 정보는 다른 정점과 해당 정점까지의 거리가 쌍으로 주어진다.

접근

가장 먼저 떠오른 방법은 무식하게 조사하는 방법이다.

정점과 정점사이의 모든 경우에 대해서 거리를 계산한다. 모든 경우에 대해서 최대 거리를 계속 갱신하여 지름을 구한다.

하지만 정점의 개수가 최대 100,000개이므로 시간과 메모리 측면에서 불가능해보인다. 따라서, 이런 경우에 대해서는 지름이 나올 수 밖에 없는 경우를 생각해보았다.

위 트리는 문제의 테스트 케이스에 대한 트리이다. 위 경우에 대해서 트리의 지름은 1 - 3 - 4 - 5로 이어지는 11이 된다.

구하는 방법은 다음과 같다. 지름의 경우 결국 두 정점간의 최장 거리인데 그렇다면 시작 정점에 대해서 가장 먼 노드의 거리들을 구하고 그 중에서 최대값을 선택하면 되는 것이다.

지름을 구하기 위해서 탐색하는 방법은 DFS를 사용하게 된다. 시작 정점이 1인 경우를 보자. DFS를 수행해 1 - 3 - 4까지 와서 5와 2로 가는 분기를 만난다. 이 중에서 거리의 최대값은 두 정점간의 거리 중 더 큰 값을 선택하면 되는 것이다. 따라서, 최장거리는 1->5, 11이 되는 것이다.

다음으로 2의 경우를 보자. 2는 4에서 3또는 5로 가는 분기를 만난다. 이전에 1의 경우에는 분기에서 더 큰 값을 선택했지만 2는 4 - 3으로 가면 1로도 갈 수 있기 때문에 이 경우에는 2 - 4 - 5와 2 - 4 - 3 - 1의 두 가지 경우를 비교해야 한다. 2->1인 경우 더 많은 정점을 지나가지만 2->5의 경우가 더 큰 값으로 10을 가지기 때문에 최장거리는 2->5, 10이 된다.

이와 같이 모든 경우를 보면 다음과 같다.
1 -> 5 : 11
2 -> 5 : 10
3 -> 5 : 9
4 -> 5 : 6
5 -> 1 : 11

따라서, 트리의 지름은 1->5, 11이 된다. 모든 경우에 대해서 잘 살펴보면 가장 먼 노드들이 모두 지름의 두 정점을 가리킨다는 것이다. 이 뜻은 모든 경우가 결국 지름의 경로를 일부분 포함한다는 것이 된다.

여기서, 2의 경우 2 - 4의 거리가 매우 커지는 경우에 대해서 의문을 가질 수 있다. 그런 경우에는 트리의 지름은 2->5로 바뀌는데 이와 마찬가지로 모든 시작 정점에 대해서도 결과가 바뀌기 때문에 문제가 발생하지 않는다.

여기까지의 내용을 정리하자면
1. 트리의 지름은 모든 시작점에 대해서 가장 먼 정점의 거리 중 최대값을 선택하는 것으로 표현될 수 있다.
2. 1에 대해, 모든 경우의 가장 먼 정점은 트리의 지름에 대한 정점을 포함하게 되어있다.

위 내용을 토대로 다음과 같이 트리의 정점을 구할 수 있다.
1. 아무 시작 정점에 대해서 DFS를 수행하여 가장 먼 정점을 구한다.
2. 1에서 구한 가장 먼 정점을 시작 정점으로 다시 DFS를 수행한다.
3. 2에서 실행한 DFS의 결과로 트리의 지름을 구할 수 있다.

코드

package java_baekjoon;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class prob1167 {
    static int V;
    static ArrayList<node>[] list;
    static boolean[] visited;
    static int max;
    static int far_node;

    public static class node{
        int node;
        int distance;

        public node(int node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        V = sc.nextInt();

        list = new ArrayList[V+1];  //제네릭 type safety 문제 발생
        visited = new boolean[V+1];

        for(int i=1;i<V+1;i++){
            list[i] = new ArrayList<node>();
        }

        for(int i=0;i<V;i++){
            int vertex = sc.nextInt();

            while(true){
                int next = sc.nextInt();
                if(next == -1){
                    break;
                }
                int distance = sc.nextInt();

                list[vertex].add(new node(next, distance));
            }
        }

        visited[1] = true;
        DFS(1, 0);

        Arrays.fill(visited, false);

        visited[far_node] = true;
        DFS(far_node, 0);

        System.out.println(max);
        

        sc.close();
        return;
    }    
    static public void DFS(int node, int distance){
        if(distance > max){
            max = distance;
            far_node = node;
        }

        for(int i=0;i<list[node].size();i++){
            node n = list[node].get(i);

            if(!visited[n.node]){
                visited[n.node] = true;
                DFS(n.node, distance + n.distance);
            }
        }
    }
}

결과

참고자료

https://moonsbeen.tistory.com/101