[백준 Gold 1] 2213 트리의 독립집합 - Java

문제링크 : https://www.acmicpc.net/problem/2213

2213번: 트리의 독립집합

 

접근 과정 : 

• 이전에 풀었던, '트리에서의 다이나믹 프로그래밍' 접근을 통해서 문제를 해결하려고 했다.
• 추가적으로 고민했던 부분은 독립 집합의 원소들을 추적하는 부분이었다.
• 결국 현재 정점의 독립 집합 포함 여부에 따라서 연결된 다음 정점의 포함여부가 결정되기에, 이 부분을 고려해서 작성했다.
• DP[][] : i번 정점의 독립집합 포함 여부   , [n+1][2]

 

소스 코드 및 결과 :

package BOJ;

/* 
    트리의 독립집합
*/

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

public class BOJ2213 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        init();

        findDP(1);

        StringBuilder answer = new StringBuilder();
        group = new ArrayList<>();
        visit = new boolean[n+1];
        if (dp[1][0]> dp[1][1]) { 
            answer.append(dp[1][0]).append("\n");           
            trace(1, false);
        }else{
            answer.append(dp[1][1]).append("\n");           
            trace(1, true);
        }

        Collections.sort(group);
        for(int v : group){
            answer.append(v).append(" ");
        }

        System.out.println(answer.toString().trim());

    }

    static int n;
    static int[] w;
    static Node[] G;
    static int[][] dp; // i의 독립 집합 여부에 따른 최대 가중치
    static boolean[] visit;
    static List<Integer> group;

    static void init() throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        w = new int[n + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            w[i] = Integer.parseInt(st.nextToken());
        }

        G = new Node[n + 1];

        for (int i = 1; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            insert(a, b);
            insert(b, a);
        }

        dp = new int[n + 1][2];
        visit = new boolean[n + 1];
    }

    private static class Node {

        int num;
        Node parent;

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

    static void insert(int p, int c) {
        if (G[p] == null) {
            G[p] = new Node(c, null);
        } else {
            G[p] = new Node(c, G[p]);
        }
    }

    static void findDP(int x) {

        visit[x] = true;
        dp[x][1] = w[x];

        Node v = G[x];
        while (v != null) {

            if (visit[v.num]) {
                v = v.parent;
                continue;
            }

            findDP(v.num);

            dp[x][0] += Math.max(dp[v.num][0], dp[v.num][1]);
            dp[x][1] += dp[v.num][0];

            v = v.parent;
        }
    }

    static void trace(int x, boolean state) {

        visit[x] = true;

        if (state) {
            group.add(x);

            Node v = G[x];
            while (v != null) {

                if (visit[v.num]) {
                    v = v.parent;
                    continue;
                }

                trace(v.num, false);

                v = v.parent;
            }
           

        } else {

            Node v = G[x];
            while (v != null) {

                if (visit[v.num]) {
                    v = v.parent;
                    continue;
                }

                if (dp[v.num][1] > dp[v.num][0]) {
                    trace(v.num, true);
                } else {
                    trace(v.num, false);
                }

                v = v.parent;
            }

        }

    }

}

 

P.S

사실 트리관련 문제를 조금 어려워하는 편이다.

아무래도, 트리 구조를 활용하려면 클래스를 작성해야 하고 필요한 메소드를 직접 만들어야 해서 약간의 부담감을 느끼는 것 같다.

특히 코딩테스트를 할 때에는 새로운 클래스 생성을 좀 지양하는 편이다..

 

이번 문제 역식, 최근에 트리에서의 DP 활용문제를 많이 풀면서 머리에 때려박아서 가능하지 않았나 싶다..

미래의 내가 이러한 문제를 다시 풀어도 비슷하게 접근할 수 있기를 바래본다.