[백준/java] 25515번 - 트리 노드 합의 최댓값

[ 문제 ]

[ 구현 ]

 

최근 트리 dp 문제들을 풀어보기 시작했다.

기본적으로 트리가 모든 노드들이 연결된 사이클 없는 그래프이므로
루트에서부터 dfs를 통해 탐색하되, 해당 서브트리를 기준으로 해당 시점에 최적이라고 생각되는 부분을 기록해서 전체를 이룬다.

이 문제의 경우 전체 노드들을 선택적으로 방문하여더해서 최대를 만들어야 했으므로

해당 서브트리에 속한 노드들의 최대 합이 음수인 경우는 최적의 해 구성에서 제외하도록 신경써주는 것이 포인트였다.

 

dp[idx] = Math.max(dp[idx], dp[idx] + dp[adjIdx]);
이 부분에서 현재 노드를 루트로하는 서브트리의 노드들의 합을 구성할 때, 자식을 루트로 하는 서브트리의 노드들의 합이 어떻게 해도 음수인 경우 최적의 해 구성에서 제외하는 것을 알 수 있다.

[ 코드 ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int n;
    static List<List<Integer>> tree = new ArrayList<>();
    static int[] score;     // 각 노드에 적힌 정수
    static long[] dp;    // 해당 인덱스 노드를 루트로 한 서브트리의 정수 합 최댓값
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    private static void readInput() throws IOException {
        n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            tree.add(new ArrayList<>());
        }

        score = new int[n];
        dp = new long[n];

        int p,c;

        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            p = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            tree.get(p).add(c);
            tree.get(c).add(p);
        }

        st = new StringTokenizer(br.readLine());

        int x = 0;
        while(st.hasMoreTokens()) {
            score[x] = Integer.parseInt(st.nextToken());
            x++;
        }
    }

    private static void dfs(int idx, int prev) {
        if (dp[idx] != 0) return;

        dp[idx] = score[idx];

        for (int adjIdx : tree.get(idx)) {
            if (prev != adjIdx) {   // 부모 노드를 다시 방문하는 경우를 방지
                dfs(adjIdx, idx);
                dp[idx] = Math.max(dp[idx], dp[idx] + dp[adjIdx]);  // 하위 서브트리 정점들의 합이 음수인 경우 포함하지 않아야 함
            }
        }
    }

    private static void printAnswer() {
        StringBuilder sb = new StringBuilder();
        sb.append(dp[0]);
        System.out.println(sb.toString());
    }

    private static void solution() throws IOException {
        readInput();
        dfs(0, -1); // 루트의 부모는 없으므로 -1
        printAnswer();
    }

    public static void main(String[] args) throws IOException {
        Main.solution();
    }
}

 

[ 마무리 및 느낀 점 ]

 

좀 더 심화된 트리 dp문제를 풀어보며 맛을 봐야겠다.