[백준] 1967번. 트리의 지름(JAVA)

문제

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

---

풀이(30분)

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

public class Main {

    static List<List<Node>> nodes; // 인접 리스트
    static int[][] dp; // 정답을 담을 dp

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        nodes = new ArrayList<>();
        // 0열 : 해당 노드에서 좌 우에 따른 최댓값
        // 1열 : 해당 노드에서 만들 수 있는 지름의 최댓값
        dp = new int[n+1][2];

        for (int i = 0; i <= n; i++) {
            nodes.add(new ArrayList<>()); // 각 노드의 자식들을 담을 리스트 초기화
        }

        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            nodes.get(parent).add(new Node(child, cost)); // 아니라 리스트 접근
        }

        dfs(1);

        int max = 0;
        for (int i = 1; i <= n; i++) {
            max = Math.max(max, dp[i][1]); // 모든 노드별로 지름의 최댓값을 탐색
        }

        System.out.println(max);
    }

    static int dfs(int parent) {
        if (nodes.get(parent).size() == 0) { // 끝 노드에 도달했다면
            return 0;
        }

        if(dp[parent][0] != 0){ // 탐색된 적이 있다면
            return dp[parent][0];
        }

        int max = 0; // 노드에서 뻗어나갈 수 있는 최댓값
        int secondMax = 0; // 지름 최댓값을 위한 두번째 최댓값

        for(int i = 0; i < nodes.get(parent).size(); i++){ // 사이즈만큼 반복
            int num = dfs(nodes.get(parent).get(i).num) + nodes.get(parent).get(i).cost;
            if(num >= max){
                secondMax = max;
                max = num;
                continue;
            }
            if(num > secondMax){
                secondMax = num;
            }
        }

        dp[parent][0] = max;
        dp[parent][1] = max + secondMax;
        return max;
    }

    static class Node {
        int num;
        int cost;

        public Node(int num, int cost) {
            this.num = num;
            this.cost = cost;
        }
    }
}

---

문제 풀이 전략

 

각 노드별로 dfs를 통해 최대로 만들어 낼 수 있는 길이에 대해 탐색을 한다.

 

이때 dp를 적용하는데 dp에 두 가지 정보를 각각 저장한다.

1. 0열 : 각 노드에서 자식 노드로 뻗어나갈 때의 최댓값(문제의 5번 노드라 치면 15를 저장)

2. 1열 : 각 노드에서 지름을 만들 때의 최댓값(문제의 5번 노드라 치면 19를 저장)

 

이런 식으로 모든 노드에 대해 정보를 저장한 뒤, dp를 순차 조회하며 최댓값을 출력한다.