JAVA 백준 1167 트리의 지름 (트리)

 

 

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

---

문제

1. 첫째 줄에 트리의 정점 개수 V ( 2 <=  V <= 100000) 가 주어진다.
2. 둘째 줄부터 V개의 줄에 간선의 정보가 주어진다.
3. 정점 번호는 1부터 V까지 매겨진다.
4. 간선의 정보는 정점 정보와 간선 정보의 정수 두 개로 연속하여 입력되고 각 줄의 입력의 마지막에는 -1이 들어온다.
5. 임의의 두 점 사이의 거리 중 가장 긴 것의 거리를 답으로 출력한다.

---

트리의 지름 1967번과 다를 게 별로 없는 것 같은 문제이다.

 

다만 트리의 정점 개수에서 차이가 있다.

1967번은 트리의 정점이 최대 10000개이고 1167번은 트리의 정점이 최대 100000개로 10배 차이가 나서 똑같이 푼다면 시간 초과가 난다.

시간 초과를 피하기 위하여 노드의 개수를 줄일 어떠한 조건이 더 필요한 문제이다.

 

 

 

기존의 트리의 지름(1967번)을 수정한 최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static boolean[] visited;
    public static int max = 0;
    public static int last = 0;

    public static void dfs(ArrayList<Node>[] list, int s, int sum) {
        visited[s] = true;
        if (sum > max) {
            max = sum;
            last = s;
        }

        ArrayList<Node> temp = list[s];
        for (Node value : temp) {
            if (!visited[value.data]) {
                dfs(list, value.data, sum + value.weight);
            }
        }
    }

    public static class Node {
        int data;
        int weight;

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


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int V = Integer.parseInt(br.readLine());

        ArrayList<Node>[] list = new ArrayList[V + 1];
        visited = new boolean[V + 1];

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

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

            int num = Integer.parseInt(st.nextToken());

            while (true) {
                int data = Integer.parseInt(st.nextToken());
                if (data == -1) {
                    break;
                } else {
                    int weight = Integer.parseInt(st.nextToken());
                    list[num].add(new Node(data, weight));
                }
            }
        }

        for (int i = 1; i < V + 1; i++) {
            if (list[i].size() == 1) {
                visited = new boolean[V + 1];
                dfs(list, i, 0);
                break;
            }
        }

        visited = new boolean[V + 1];
        dfs(list, last, 0);

        System.out.println(max);
    }
}

 

 

 

예제를 그림으로 그려보면 다음과 같다.

 

최장 루트는 1 - 3 - 4 - 5로 11이다.

그 다음으로 긴 루트는  1 - 3 - 4 - 2로 9이다.

 

이 둘을 비교해보면 앞부분인 1 - 3 - 4는 같은 루트를 사용하고 4에서 두 갈래로 분기한다.

따라서 같은 루트를 여러 번 계산할 필요가 없기 때문에 1번을 계산하면 3번 4번을 계산하지 않아도 된다.

 

다른 노드에서 시작하더라도 똑같다.

2에서 시작해 최장 루트를 찾으면 2 - 5로 10이다.

여기서 중요한 것은 11이라는 더 긴 루트가 있기 때문에 중요한 것은 이것이다.

백트래킹을 통해 반대로 다시 최장 루트를 구하는 것이다.

가장 큰 가중치를 가진 간선의 리프노드를 구했으므로 최장 루트의 리프 노드인 5를 시작으로 다시 dfs 알고리즘을 돌리면 최종 정답인 11이 나올 것이다.

 

따라서 리스트 중 임의의 노드로 리프 노드를 고르기 위해 간선 리스트의 길이가 1인 노드 중 가장 먼저 나오는 것을 골라 dfs를 고른 후 최장 루트 위치에 있는 리프 노드를 찾아낸다.

그리고 이 리프 노드를 이용해 dfs 백트래킹하여 최종 정답을 얻어낼 수 있다.