🌳 트리 지름(Diameter) 구하기: 문제 풀이 회고

트리가 주어졌을 때, 트리의 지름(diameter)—서로 가장 먼 두 노드 간의 거리—를 구하는 문제를 풀면서 겪은 시행착오와 최종 해법을 정리했습니다.

---

1️⃣ 문제 요약 ✨

• 노드 수 (n \le 10{,}000).
• 간선은 “부모 → 자식” 형태로 주어지며 가중치(weight)도 함께 제공.
• 루트는 항상 1번.
• 트리의 지름(서로 가장 멀리 떨어진 두 노드 간 최대 거리)을 출력.

---

2️⃣ 첫 시도: 모든 리프 리프에서 BFS ❌

1. 리프 노드 수집

   • DFS로 트리를 순회하며 자식이 없는 노드를 모두 모아 리스트에 저장.

2. 각 리프마다 BFS

   • 각 리프를 시작점으로 모든 노드를 탐색하며,
   • 그 BFS에서 도달 가능한 최대 거리를 기록 → 가장 먼 리프 사이의 경로 중 하나를 찾음.

// (생략) addLeafNodes(), inputSetting() 등...
for (int leaf : leafNodes) {
    findByBfs(leaf);
}

❗️ 문제점

• 리프 개수 (L)가 최악에 약 (N)개일 수 있어서
• (\,O(L\times N)=O(N^2)) 연산 → (N=10{,}000)일 때 1억 회 이상 반복
• Java 상수 오버헤드까지 더해지면 시간 초과(TLE) 혹은 메모리/GC 부담 발생

---

3️⃣ 효율적 해법: “트리 지름 알고리즘” 🔑

핵심 아이디어 🚀

1. 임의의 출발점 (r)에서 가장 먼 노드 (u)를 찾으면,
   (\,u)는 지름을 이루는 두 끝점 중 하나이다.
2. 그 (u)에서 다시 가장 먼 노드 (v)까지의 거리가 바로 트리 지름이다.

이 방식은 두 번의 그래프 순회(DFS 또는 BFS)만에 (O(N))에 해결할 수 있습니다.

---

4️⃣ “가장 먼 노드는 지름의 끝점” 증명 🔍

• 지름을 이루는 두 끝점 ((u, v)) 사이 거리가 최대이므로,
• 임의의 점 (r)에서 (u), (v)까지 거리 중 큰 쪽을 고르면 반드시 (u) 또는 (v)가 선택됨
• 따라서 “(r)에서 가장 먼 노드”는 지름의 끝점

---

5️⃣ DFS vs. BFS: 어떤 탐색을 쓸까? ⚔️

• 이론적 복잡도: (\,O(N))로 동일
• 상수 계수 상 DFS(재귀)가 약간 더 경량
• 가중치 누적이나 간단한 구현 관점 → DFS가 더 직관적
• 거리 기준 순회가 필요할 땐 BFS도 무난하지만,
  재귀로 depth + weight를 전달하기 좋은 DFS를 선택했습니다.

---

6️⃣ 최종 코드 예시 (DFS) 💻

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

public class Main {
    static int N;
    static List<List<int[]>> adj = new ArrayList<>();
    static boolean[] visited;
    static int farNode, maxDist;

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

        // 인접 리스트 초기화
        for (int i = 0; i <= N; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < N - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            adj.get(p).add(new int[]{c, w});
            adj.get(c).add(new int[]{p, w});
        }

        visited = new boolean[N + 1];
        farNode = 1; maxDist = 0;

        // 1) 임의의 노드(1)에서 가장 먼 노드 u 찾기
        dfs(1, 0);
        // 2) u에서 다시 가장 먼 v 찾기
        Arrays.fill(visited, false);
        maxDist = 0;
        dfs(farNode, 0);

        // 지름 출력 🎯
        System.out.println(maxDist);
    }

    static void dfs(int curr, int dist) {
        visited[curr] = true;
        if (dist > maxDist) {
            maxDist = dist;
            farNode = curr;
        }
        for (int[] edge : adj.get(curr)) {
            int nxt = edge[0], w = edge[1];
            if (!visited[nxt]) {
                dfs(nxt, dist + w);
            }
        }
    }
}

---

7️⃣ BFS 대안 예시 🌐

static int[] bfs(int start) {
    boolean[] vis = new boolean[N + 1];
    Queue<int[]> q = new ArrayDeque<>();
    q.add(new int[]{start, 0});
    vis[start] = true;

    int far = start, maxD = 0;
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int u = cur[0], d = cur[1];
        if (d > maxD) {
            maxD = d;
            far  = u;
        }
        for (int[] e : adj.get(u)) {
            int v = e[0], w = e[1];
            if (!vis[v]) {
                vis[v] = true;
                q.add(new int[]{v, d + w});
            }
        }
    }
    return new int[]{far, maxD};
}

• bfs(1) → ([u, _])
• bfs(u) → ([_, diameter])