백준 1167: 트리의 지름(Java)

💡 문제 요약

• 트리 구조의 그래프가 주어진다.
• 각 노드 간의 거리는 가중치가 있으며, 양방향이다.
• 이 트리에서 가장 먼 두 정점 간의 거리, 즉 트리의 지름을 구하는 문제.

---

🧠 핵심 개념

• 트리의 지름(Tree Diameter): 트리에서 가장 긴 경로의 길이
• 트리의 성질상, 임의의 노드에서 가장 먼 노드를 먼저 찾고,
  그 노드로부터 다시 DFS를 돌려 최대 거리를 구하면 그게 지름이다.

---

🔍 알고리즘 설계

1. 입력 파싱

• 각 정점 번호와 연결된 정점 번호 및 거리를 입력 받음
• ArrayList<Node>[] graph를 사용하여 인접 리스트 구성
  (Node는 연결된 노드 번호와 거리 정보를 포함)

2. 트리의 지름 구하기

1️⃣ DFS 1차

• 임의의 노드(예: 1번)에서 가장 멀리 있는 노드를 찾음
• 이 노드를 farthestNode 변수에 저장

2️⃣ DFS 2차

• 위에서 찾은 farthestNode에서 다시 DFS 수행
• 최대로 멀리 떨어진 거리(diameter)를 구함 → 이 값이 지름

---

✅ 전체 코드 (가독성 향상 + 변수명 정리)

import java.util.*;

public class Main {

    static List<Node>[] graph;
    static boolean[] visited;
    static int diameter = 0;
    static int farthestNode = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int from = sc.nextInt();
            while (true) {
                int to = sc.nextInt();
                if (to == -1) break;
                int cost = sc.nextInt();
                graph[from].add(new Node(to, cost));
            }
        }

        visited = new boolean[n + 1];
        dfs(1, 0);

        visited = new boolean[n + 1];
        dfs(farthestNode, 0);

        System.out.println(diameter);
    }

    static void dfs(int current, int dist) {
        if (dist > diameter) {
            diameter = dist;
            farthestNode = current;
        }

        visited[current] = true;

        for (Node neighbor : graph[current]) {
            if (!visited[neighbor.to]) {
                dfs(neighbor.to, dist + neighbor.cost);
            }
        }
    }

    static class Node {
        int to, cost;
        Node(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }
    }
}

---

✅ 전체 흐름 요약

1. 인접 리스트 구성
2. DFS(1) → 가장 먼 노드(farthestNode) 탐색
3. DFS(farthestNode) → 그 노드에서 가장 먼 거리(diameter) 탐색
4. 출력 diameter

---

📦 시간 복잡도 분석

• 정점 개수 N (1 ≤ N ≤ 100,000)
• 트리는 간선 수가 N - 1
• DFS는 O(N)으로 두 번만 수행됨 → 전체 시간복잡도 O(N)

---

📌 정리

방식	설명
접근법	DFS 두 번 수행 (임의노드 → 가장 먼 노드 → 최대 거리)
자료구조	인접 리스트(List[]), 방문 배열
핵심 로직	DFS로 거리 누적하며 가장 먼 노드 탐색