[백준 | JAVA] 1167 - 트리의 지름 (트리, DFS)

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

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

---

풀이

이 문제의 핵심 풀이방법은 DFS를 두 번 사용하는 것이다. 이 부분을 깨닫는데 꽤 많은 시간이 걸렸다.

일단 왜 DFS를 두 번 사용해야하는가에 대한 의문은 뒤로 두고, 트리의 지름을 어떻게 찾을 것인가부터 생각해보자.

알고리즘 문제를 자주 풀어본 사람들은 DFS를 사용하면 되겠구나, 하는 생각은 쉽게 했을 것이라고 생각한다. 필자는 아래와 같이 DFS를 선언하여 사용했다.

private static void dfs(int vertex, int dist) {
    for (Node child : tree.get(vertex)) {
        if(!visited[child.vertex]) {
            visited[child.vertex] = true;
            dfs(child.vertex, dist + child.dist);
        }
    }

    if(maxNode.dist < dist) {
        maxNode = new Node(vertex, dist);
    }
}

하지만 DFS를 어떻게 사용할 것인지에서 의문이 생긴다.

어떤 노드를 시작점으로 해야 트리의 지름(노드 간의 최장 거리)가 될 것인가?

이 질문에 대한 답은 트리를 그려보면 금방 알 수 있다.

위 이진트리에서 임의의 노드인 1을 시작점으로 한다고 생각해보자. 1번 노드에서 부터 DFS를 통해 가장 긴 거리를 가지는 노드는 2번 노드가 된다.

하지만 1번 노드 -> 2번 노드가 트리의 지름이 될 수는 없다. 1번 노드에는 2번 노드와는 다른 가지로 뻗어 있는 자식 노드가 하나 존재하기 때문이다.

즉, 2번 노드 → 1번 노드의 거리 > 2번 노드 → 2번 노드와는 다른 가지에 존재하는 1번 노드의 자식이 되는 것은 자명하다.

여기서 하나의 결론을 도출할 수 있다.

시작점이 되는 노드는 하나의 자식만을 가져야 한다.

그렇다면 여기서 또 하나의 의문이 생긴다.

하나의 자식만을 가지는 노드를 어떻게 구할까?

어떤 임의의 점에서 DFS를 진행하면, 시작점이 된 임의의 점에서 가장 먼 거리에 존재하는 노드를 찾을 수 있다. (이 길이가 트리의 지름이 되지 않는다는 것은 위에서 언급하였다.)

이제 "어떤 임의의 점에서 가장 먼 거리에 존재하는 노드"에 집중해보자. 이 노드는 아래와 같은 특징을 가진다.

1. 자식 노드가 하나만 존재한다.
2. 어떤 임의의 노드로부터 최장거리이다.

1번 특징은 위 질문에 대한 답이 된다.

2번 특징 또한 중요하다. 이 말은 이렇게 바꿀 수 있다. "자신과 같은 레벨(깊이)의 노드 중 최장 거리를 가진다."

따라서 이 문제의 알고리즘은 이렇게 정리할 수 있다.

 

1. 임의의 노드(일반적으로 1번 노드)에서 가장 멀리 떨어진 노드를 찾는다.
   • 이때 찾은 노드는 트리(1번 노드를 루트로 하는 트리)의 최하위 노드가 된다.
   • 1번째 DFS (임의의 노드를 시작점으로 DFS)
2. 이렇게 찾은 노드를 루트로 삼아, 다시 한 번 가장 멀리 떨어진 노드를 찾는다.
   • 이때 찾은 노드 간의 거리가 트리의 지름이 된다.
   • 2번째 DFS (1번째 DFS에서 찾은 노드를 시작점으로 DFS)

 

이해가 잘 가지 않는다면, 천천히 트리의 그림을 따라가면서 곰곰히 생각해보자.

 

코드

import java.util.*;
import java.io.*;

public class Main {

    private static List<List<Node>> tree;
    private static boolean[] visited;
    private static Node maxNode = new Node(0, 0);

    // 노드와 거리 정보를 담는 클래스
    static class Node {
        int vertex;
        int dist; // 부모 노드와의 거리

        Node(int vertex, int dist) {
            this.vertex = vertex;
            this.dist = dist;
        }
    }

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

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

        tree = new ArrayList<>();
        for (int i = 0; i <= v; i++) {
            tree.add(new ArrayList<>());
        }

        visited = new boolean[v+1];

        for (int i = 0; i < v; i++) {
            stk = new StringTokenizer(br.readLine());
            int node = Integer.parseInt(stk.nextToken());

            while(true) {
                int connectedNode = Integer.parseInt(stk.nextToken());
                if(connectedNode == -1) break;
                int dist = Integer.parseInt(stk.nextToken());

                tree.get(node).add(new Node(connectedNode, dist));
            }
        }

        visited[1] = true;
        dfs(1, 0);
        // 임의의 노드에서 가장 거리가 먼 노드 찾기
        // 이때의 거리는 트리의 지름인 아님

        Arrays.fill(visited, false);

        visited[maxNode.vertex] = true;
        dfs(maxNode.vertex, 0);
        // 임의의 노드로부터 가장 먼 거리의 노드를 루트로 dfs
        // -> 여기서 구한 거리가 트리의 지름

        System.out.println(maxNode.dist);
    }

    private static void dfs(int vertex, int dist) {
        for (Node child : tree.get(vertex)) {
            if(!visited[child.vertex]) {
                visited[child.vertex] = true;
                dfs(child.vertex, dist + child.dist);
            }
        }

        if(maxNode.dist < dist) {
            maxNode = new Node(vertex, dist);
        }
    }
}

 

---

 

여담

이 문제에서 트리를 구성할 때, 인접 리스트가 아니라 인접 행렬을 사용할 경우 메모리 초과가 나타난다.

간단히 계산해보면 당연한 결과인데, 트리의 정점의 개수(v)가 최댓값인  100,000일 경우 인접행렬로 구현시 100,000 x 100,000 x 4bytes = 40GB (int 자료형으로 노드 간의 거리를 저장한다고 했을 때)라는 어마어마한 양의 메모리를 차지하게 된다. 문제에서 주어진 최대 메모리는 $256MB$이므로 메모리 초과가 나타나는 건 당연한 결과다.

본문의 코드처럼 Node 클래스를 만들고 인접 리스트를 이용하여 트리를 구현하면, 메모리를 효율적으로 활용할 수 있다.

실제로 100MB 정도의 메모리만을 사용한 것을 확인할 수 있다.

 

문제에서 주어지는 변수의 범위를 반드시 확인하고 구현을 시작하자!