백준 1167 "트리의 지름" (JAVA)

🔍 문제링크

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

---

📌 문제 요약

• 트리의 지름: 트리에서 가장 긴 경로의 길이.
• 정점이 순서대로 주어진다는 보장이 없음.
• DFS 2번 사용하여 트리의 지름을 구함:
  1. 임의의 정점에서 가장 먼 정점을 찾음.
  2. 이 정점에서 가장 먼 정점까지의 거리가 트리의 지름.

---

🛠 풀이 및 알고리즘

1. 그래프 입력을 인접 리스트로 저장
   • 정점의 개수(v)를 입력받고, 각 정점에 연결된 노드 정보를 저장.
   • 입력이 순서대로 주어지지 않기 때문에 인접 리스트 활용.
2. DFS 1회 실행
   • 임의의 정점에서 가장 먼 정점(maxNode)을 찾음.
   • visited[] 배열을 활용하여 탐색.
3. DFS 2회 실행
   • maxNode에서 가장 먼 정점까지의 거리(temp)를 구함 → 트리의 지름.

---

💡 코드

public class Baekjoon_1167 {
    static int v, maxLen, maxNode;
    static int[] visited;
    static ArrayList<ArrayList<Info>> graph;

    static class Info {
        int node;
        int len;

        Info(int node, int len) {
            this.node = node;
            this.len = len;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        maxLen = Integer.MIN_VALUE;
        maxNode = 0;
        graph = new ArrayList<>();

        // 그래프 초기화
        for (int i = 0; i <= v; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < v; i++) {
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            while (true) {
                int a = Integer.parseInt(st.nextToken());
                if (a == -1) {
                    break;
                }
                int b = Integer.parseInt(st.nextToken());
                graph.get(num).add(new Info(a, b));
            }
        }
        // 1. 임의의 정점에서 가장 먼 정점 찾기
        visited = new int[v + 1];
        maxLen = 0;
        dfs(1, 0);

        //  2. 찾은 정점에서 가장 먼 정점까지 거리 구하기
        visited = new int[v + 1];
        maxLen = 0;
        dfs(maxNode, 0);

        System.out.println(maxLen);
    }

    static void dfs(int s, int sum) {
        visited[s] = 1;
        if (maxLen < sum) {
            maxLen = sum;
            maxNode = s;
        }
        for (Info info : graph.get(s)) {
            if (visited[info.node] == 0) {
                dfs(info.node, sum + info.len);
            }
        }
    }
}

---

🏆 시간 복잡도 분석

• DFS 1회: O(V)
• DFS 2회: O(V)
• 총 시간 복잡도: O(2V) = O(V)