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

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

이제 그래프 문제를 보면 시간초과가 날까봐.. 최대한 중복되는 경로를 안갖도록 고민하다가 빅오 O(n)으로 해결했다.

리프 노드에서 리프 노드로 이동하는 지름이 최대가 되도록 하는 방법을 찾기 위해 두 개의 값을 확인하면 된다.

• 자식 노드 중 가장 큰 값
• 자식 노드 중 가장 큰 값 2개 합친 값

자식 노드 중 가장 큰 값은 리프 노드 ~ 현재 노드까지 중에서 가장 큰 지름을 가지는 경로이고,

자식 노드 중 가장 큰 값 2개 합친 값은 현재 노드를 기준으로 꺾여 리프 노드 ~ 리프 노드까지 중에서 가장 큰 지름을 가지는 경로이다. 

 

따라서 처음 입력값도 자식 노드를 가지는 연결리스트로 선언해 주었다.

int N = Integer.parseInt(br.readLine());

List<Tuple>[] list = new ArrayList[N+1];
for (int i = 1; i <= N; i++) {
    list[i] = new ArrayList<Tuple>();
}

for (int i = 1; i < N; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());

    int v1 = Integer.parseInt(st.nextToken());
    int v2 = Integer.parseInt(st.nextToken());
    int value = Integer.parseInt(st.nextToken());

    list[v1].add(new Tuple(v2, value));
}

 

리프 노드부터 현재 노드까지 확인해야 하므로 dp 알고리즘을 이용했다.

따라서 Main 문에서 루트 노드인 1부터 getLen 함수를 호출해서 자식 노드부터 먼저  dp 값이 채워지게 된다.

public static void getLen (List<Tuple>[] list, int v) {
    int maxFirst = 0;
    int maxSecond = 0;

    for (Tuple tuple : list[v]) {
        int i = tuple.child;
        int value = tuple.value;

        getLen(list, i);

        if (maxFirst < dp[i] + value) {
            maxSecond = maxFirst;
            maxFirst = dp[i] + value;
        }
        else {
            maxSecond = Math.max(maxSecond, dp[i] + value);
        }
    }
    dp[v] = maxFirst;

    // 자식 노드 중 가장 큰 값 vs 현재 노드를 기준으로 꺽인 경로
    result = Math.max(result, Math.max(dp[v], (maxFirst + maxSecond)));
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B1967.java

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

public class Main {
    static int result;
    static int[] dp;

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        List<Tuple>[] list = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<Tuple>();
        }

        for (int i = 1; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            list[v1].add(new Tuple(v2, value));
        }

        dp = new int[N+1];

        getLen(list, 1);

        bw.write(result+"");

        br.close();
        bw.flush();
        bw.close();
    }

    public static void getLen (List<Tuple>[] list, int v) {
        int maxFirst = 0;
        int maxSecond = 0;

        for (Tuple tuple : list[v]) {
            int i = tuple.child;
            int value = tuple.value;

            getLen(list, i);

            if (maxFirst < dp[i] + value) {
                maxSecond = maxFirst;
                maxFirst = dp[i] + value;
            }
            else {
                maxSecond = Math.max(maxSecond, dp[i] + value);
            }
        }
        dp[v] = maxFirst;
        
        // 자식 노드 중 가장 큰 값 vs 현재 노드를 기준으로 꺽인 경로
        result = Math.max(result, Math.max(dp[v], (maxFirst + maxSecond)));
    }

    public static class Tuple {
        int child;
        int value;

        public Tuple (int child, int value) {
            this.child = child;
            this.value = value;
        }
    }
}

---

4. 결과 및 회고

그래프는 루트 노드에서 리프 노드까지, 혹은 리프 노드에서 루트 노드까지 확인하면 풀리는 문제들이 많은 것 같기도?

첨엔 그래프 문제가 어려웠는데 점점 풀다 보니 조금은 덤빌만한 것 같다.