[백준 JAVA] 1967번: 트리의 지름

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

 

이번 문제는 “트리의 지름”인데, 아이디어는 맞았지만 구현에서 틀린 케이스였다.

 

문제 접근

트리의 지름은 “가장 먼 두 노드 사이의 거리”다.
이걸 DFS로 풀 때 핵심 아이디어는 다음이다.

각 노드에서

• 아래로 내려가는 최대 경로 길이들을 구하고
• 그 중 가장 긴 두 개를 더해서 지름 후보를 만든다

그리고 부모에게는 “가장 긴 하나만” 반환한다.

이 구조를 재귀로 구현하면 자연스럽게 트리 DP 형태가 된다.

 

내 풀이 아이디어

나는 다음과 같은 방식으로 접근했다.

• maxLength(u) : u에서 시작해서 아래로 내려가는 최대 길이 반환
• 각 노드에서 자식들을 순회하면서
  • 가장 긴 경로 (first)
  • 두 번째로 긴 경로 (second)
    를 구한다
• first + second로 지름 후보를 갱신한다

이 아이디어 자체는 정답 접근이다.

 

코드

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

public class Main {
    static int N, max;
    static List<int[]>[] tree;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        tree = new List[N + 1];
        for (int i = 1; i <= N; i++) tree[i] = new ArrayList<>();
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            tree[p].add(new int[] {c, w});
        }

        max = 0;
        maxLength(1);

        System.out.println(max);
    }

    private static int maxLength(int u) {
        int first = 0;
        int second = 0;
        for (int[] next : tree[u]) {
            int v = next[0];
            int w = next[1];

            int length = maxLength(v) + w;

            if (length > first) {
                second = first;
                first = length;
            } else if (length > second) {
                second = length;
            }
        }

        max = Math.max(max, first + second);
        return first;
    }
}

 

핵심 개념 정리

이 풀이에서 중요한 포인트는 딱 두 개다.

1. 부모에게 넘기는 값
   → 현재 노드에서 아래로 내려가는 최대 경로 하나
2. 지름 갱신
   → 현재 노드를 기준으로 가장 긴 두 경로의 합

지름은 한 줄 경로이기 때문에 한 노드에서 여러 갈래를 동시에 사용할 수 없고 항상 두 방향만 선택된다.

 

느낀 점

아이디어는 맞았는데 구현에서 틀렸다.

특히

• second 갱신 실수
• 대입 연산 (first = second) 같은 실수

이런 부분이 실제 코딩 테스트에서 가장 많이 터지는 유형이다.

이번 문제는 개념 부족이 아니라
디테일에서 틀린 케이스였다.

이 단계에서는 문제를 더 많이 푸는 것도 중요하지만
코드를 작성할 때 “값이 어떻게 변하는지”를 한 번씩 추적하는 습관이 더 중요한 것 같다.