[백준/Java] 1167 트리의 지름

🔗 문제 링크: https://www.acmicpc.net/problem/1167

🔍 해결 과정

문제 예시를 바탕으로 트리를 만들어보면 다음과 같습니다.

여기에서 1번 노드와 6번 노드까지의 거리가 11로 트리에서 가장 최대의 거리를 나타내므로 11이 이 트리의 지름값이라고 할 수가 있습니다.

 

만약 노드 V의 최대 개수가 최대 10만개가 아니고 매우 작은 값이었다면 단순하게 모든 노드를 시작점으로 했을 때의 dfs를 돌려서 최대 거리값을 구했겠지만 노드의 개수가 최대 10만개이기 때문에 모든 노드마다 dfs를 돌리기에는 시간 복잡도 O(V^2)이 나오기 때문에 다른 방식을 고민하는 일에 시간을 많이 쓴 문제였습니다.

 

과정을 세우기에 앞서서 다음과 같은 공식을 알아야 합니다.

1️⃣ 임의의 노드 a를 한 시작점으로 dfs를 통해 가장 거리가 먼 노드 b를 구한다.
2️⃣ 노드 b로부터 다시 dfs를 통해 가장 거리가 먼 노드 d를 구한다.
3️⃣ 노드 b와 노드 d 사이의 거리가 트리에서 최댓값이 되므로 곧 트리의 지름이 된다 

 

 

위 공식에 대한 증명은 다음 사이트를 참고 하였습니다.

https://bedamino.tistory.com/15

[백준][BOJ1967] 트리의 지름

 

임의의 노드에서 dfs를 활용하여 가장 거리가 먼 노드 a를 선택하고 다시 노드 a에서 dfs를 활용하여 거리가 먼 b를 선택을 함으로써 시간 복잡도를 O(V)로 유지할 수가 있었습니다.

 

---

✏️ 코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

class Node {
    private final int index;
    private final int cost;

    public Node(int index, int cost) {
        this.index = index;
        this.cost = cost;
    }

    public int getIndex() {
        return index;
    }

    public int getCost() {
        return cost;
    }
}

public class Main {

    private static final int END = -1;
    private static List<Node>[] trees = new ArrayList[100_001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int v = Integer.parseInt(br.readLine());

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

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

            while (st.hasMoreTokens()) {
                int otherNode = Integer.parseInt(st.nextToken());
                if (otherNode == END) {
                    break;
                }

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

                trees[curNode].add(new Node(otherNode, cost));
            }
        }

        int[] firstNode = getMostCostNode(1, 0, new boolean[v + 1]);

        bw.write(Integer.toString(getMostCostNode(firstNode[0], 0, new boolean[v + 1])[1]));
        bw.flush();
        bw.close();
    }

    private static int[] getMostCostNode(int nodeNumber, int curCost, boolean[] visited) {
        visited[nodeNumber] = true;
        int[] result = {nodeNumber, curCost};

        for (Node node : trees[nodeNumber]) {
            int nextNumber = node.getIndex();
            int nextCost = node.getCost();

            if (visited[nextNumber]) {
                continue;
            }

            int[] temp = getMostCostNode(nextNumber, nextCost + curCost, visited);

            if (temp[1] > result[1]) {
                result = temp;
            }
        }

        return result;
    }
}