백준 1167: 트리의 지름 [골드 Ⅱ / Java]

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

1167번: 트리의 지름

---

 

 

Solution

DFS, BFS

 

 

문제에서 노드의 개수 N이 최대 100,000 이고, 싸이클이 없는 트리의 엣지 개수는 N - 1 이다.

노드 간 거리를 다 계산하고 비교해서 트리의 지름을 구하면 총 연산 횟수는 O(N²) 가 되어 시간 초과가 발생한다.

 

 

대신 이 연산을 직접 완전 탐색해서 모든 거리를 계산하고 공통점을 관찰해 보면,

어떤 노드에서든지 트리의 지름의 노드까지 거리가 가장 길다는 것을 알 수 있다.

 

따라서 임의의 노드에서 가장 먼 노드를 찾아서 트리의 지름의 양 끝 노드 중 하나를 찾고,

또 그 노드에서 가장 먼 노드를 찾으면 트리의 지름을 구할 수 있다.

 

 

 

 

 

물론 이렇게 목적 없이 나열해 보고 공통점을 찾는 것도 해법 중 하나지만,

완전 탐색을 하지 않고 관찰로 일반화 해보자.

 

 

 

트리의 특징은 다음과 같다.

 

1) 어떤 노드가 root이든지 트리의 지름(최장 거리)는 두 leaf node 사이 거리이다.

2) 트리의 지름에는 간선이 많거나 길이가 긴 간선이 있다.

3) 트리에서 두 노드 사이 경로와 거리는 유일하다.

 

이 특징을 이용해서 풀이해 보자.

 

 

 

 

B-C 가 지름인 임의의 트리를 가정해 보자. Root  노드를 고려하지 않고 트리를 펼쳐서 생각할 수 있다.

 

 

 

 

특징적인 점은 트리의 지름 위 노드들이다. 이들의 특징을 추출해야 한다.

 

 

B - M - N - A - C

 

B-C 의 경로이다.

경로를 따라가며 다음과 같은 사실을 알아낼 수 있다.

 

1) M을 기준으로 M ~ {B > H}, M ~ {C > H, G, E, F}

2) N을 기준으로 N ~ {B > H, E, F}, N ~ {C > G, E, F} 

3) A를 기준으로 A ~ {B > H, E, F}, A ~ {C > G}

 

 

 

즉, M, N, A 를 root node 위치로 집어서 올렸다고 생각할 수 있다.

이때 root node 에서의 거리가, 동일 방향의 주변 leaf node 보다 지름의 노드까지 거리가 더 멀다.

 

 

 

 

 

일단 최장 거리를 알려면 모든 거리는 아니라더라도 몇 개는 구해봐야 하는 건 당연하다.

 

따라서 임의의 노드 E에서 leaf node 들까지 거리를 비교해 보는데,

이때 갈림길인 D → N → M, A ... 기준으로 한다.

 

 

 

D를 기준으로 할 때,

N을 기준으로 N ~ {B > H, E, F} 였기 때문에 D에서부터 거리는 {B, H, E, F} 중 당연히 B가 최대이다.

N을 기준으로 N ~ {C > G, E, F} 였기 때문에 D에서부터 거리는 {C, G, E, F} 중 당연히 C가 최대이다.

 

따라서 E에서부터 B나 C까지 거리가 최대이다.

 

 

 

이는 비록 D가 B-C 중간 노드로써 비교 기준이 되진 않았지만,

D에 달린 E와 F가 비교 대상으로써 트리의 지름인 B와 C 보다 작다는 것을 알기 때문이다.

 

 

 

 

따라서 이것을 일반화할 수 있는가 했을 때

N ~ {C > G, F, E} 에서 N-C 밖의 노드인 D에서 비교할 땐, D ~ {E, F} 는 경로가 짧아지므로 당연히 D-C 보다 작은 것이고

N ~ {C > G} 중간 노드인 A에서 비교할 땐, 당연히 A-C 가 A-G 보다 클 것이다.

 

 

결론적으로 어떤 노드에서든지 트리의 지름의 노드까지 거리가 최대임을 알 수 있다.

 

 

 

 

이런 생각을 잠깐 했는데, 지름인 B, C 가 아닌 D-F 거리가 모든 엣지 통틀어서 최댓값이라고 가정하면,

갈림길에서 B, C 가 아닌 F 가 선택될 수 있지 않을까 고민했다.

 

 

 

N ~ {B > H, E, F} 였으므로 D를 기준으로 D-B거리가 최대이고 D-F 거리도 크겠지만,

B-N 거리 + N-C 거리 가 더 컸기 때문에 B-C가 지름이 되었을 것이다.

 

 

 

어떤 leaf node 까지 거리는 중간 노드를 거쳐야 한다. 즉, 엣지 하나가 아니라 가중치의 합이 중요하다.

또한 비교하는 것 또한 상대적이다. 어떤 노드를 기준으로 하느냐에 따라 다르다.

F가 더 큰 것은 D-F > D-E 일 때 뿐이다. N에서는 N-C > N-F 이다.

 

 

 

 

사실 이런 생각은 문제 외의 것이다.

트리의 지름은 엣지의 가중치를 지정해 주자마자 정해진다. 이런 비교는 고려 대상이 아니다.

이미 B-C 가 최대이고, 그러기 때문에 N ~ {C > G, E, F}, {B > H, E, F} 이고, 이걸 그냥 문제풀이에 사용하기만 하면 된다.

 

 

 

 

트리의 특징을 이해하고 활용하는 문제다.

 

DFS 와 BFS 로 풀 수 있어서 자료구조를 다양하게 구성할 수 있다.

다만 100,000 x 100,000 이차원 배열을 생성했을 때, 메모리 제한이 256Mb 일 때 메모리 초과가 나는 걸 알 수 있었다.

 

 

 

 

 

Code

 

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

public class Main {

    static ArrayList<Node>[] tree;
    static boolean[] visited;
    static int[] dist;
//    static int[][] weight; // OOM

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

        int V = Integer.parseInt(st.nextToken());
        tree = new ArrayList[V + 1];
        for (int i = 1; i <= V; i++) tree[i] = new ArrayList<>();

        for (int i = 1; i <= V; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()), b;
            while ((b = Integer.parseInt(st.nextToken())) != -1) {
                int w = Integer.parseInt(st.nextToken());
                tree[a].add(new Node(b, w)); // 양방향
            }
        }

        dist = new int[V + 1]; // 1 에서부터 거리
        visited = new boolean[V + 1];
//        dfs(1);
        dfs(1, 0);
//        bfs(1);
        int max_idx = 1;
        for (int i = 2; i <= V; i++) max_idx = dist[max_idx] > dist[i] ? max_idx : i;

        dist = new int[V + 1]; // max_idx 에서부터 거리
        visited = new boolean[V + 1];
//        dfs(max_idx);
        dfs(max_idx, 0);
//        bfs(max_idx);

        Arrays.sort(dist);
        System.out.println(dist[V]);
    }

    static void dfs(int v, int d) {
        visited[v] = true;

        for (Node next : tree[v]) {
            if (!visited[next.e]) dfs(next.e, d + next.w);
        }
        if (tree[v].size() == 1) dist[v] = d; // leaf node 만 필요.
    }

    static void dfs(int v) {
        visited[v] = true;

        for (Node next : tree[v]) {
            if (visited[next.e]) continue;

            dist[next.e] = dist[v] + next.w;
            dfs(next.e);
        }
    }

    static void bfs(int s) {
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        visited[s] = true;

        while (!q.isEmpty()) {
            int v = q.poll();

            for (Node next : tree[v]) {
                if (visited[next.e]) continue;

                dist[next.e] = dist[v] + next.w;
                q.add(next.e);
                visited[next.e] = true;
            }

        }
    }

    static class Node {
        int e, w;

        Node(int e, int w) {
            this.e = e;
            this.w = w;
        }
    }

}