백준 : 2113 java

트리의 독립집합 문제는 메모이제이션을 이용해서 풀었다.

 

기본적으로 1번노드에서 시작해 그래프를 탐색하는데 현재 노드를 선택/비선택 두가지 가지로 나누어서 메오이제이션을 채울 수있다.

 

그리고 이번 노드에서 선택했다면 인접한 노드는 선택하면 안되고 만약 선택하지 않았다면 선택해도 되고 안해도 된다.

 

package algo;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class B2113 {
    static int N;
    static int W[];
    static int dp[][];
 
    static class Pair {
        int node;
        int t;
 
        public Pair(int node, int t) {
            super();
            this.node = node;
            this.t = t;
        }
    }
 
    static ArrayList<Integer> edge[];
    static ArrayList<Pair> p[][];
    static ArrayList<Integer> ans;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        // ---------------------Input------------------------
        N = Integer.parseInt(br.readLine());
        W = new int[N + 1];
        dp = new int[2][N + 1];
        st = new StringTokenizer(br.readLine());
 
        for (int i = 1; i <= N; i++)
            W[i] = Integer.parseInt(st.nextToken());
 
        edge = new ArrayList[N + 1];
        p = new ArrayList[N + 1][2];
 
        // 0 은 false 1 은 true
        for (int n = 1; n <= N; n++) {
            edge[n] = new ArrayList<Integer>();
            p[n][0] = new ArrayList<Pair>();
            p[n][1] = new ArrayList<Pair>();
        }
 
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            edge[u].add(v);
            edge[v].add(u);
        }
 
        // ---------------------------------------------
 
        int start = Solve();
        // start로 시작해서 ans에 답리스트를 채우기
        ans = new ArrayList<Integer>();
        StringBuilder sb= new StringBuilder();
        
        sb.append(getValue(1, start)).append('\n');
        Collections.sort(ans);
        for(int n : ans) {
            sb.append(n).append(' ');
        }
        System.out.print(sb.toString());
    }
 
    public static int getValue(int n, int t) {
        int sum = 0;
        if (t == 1) {
            ans.add(n);
            sum = W[n];
        }
        for (Pair next : p[n][t]) {
            sum+=getValue(next.node, next.t);
        }
 
        return sum;
    }
 
    static boolean visit[];
 
    public static int Solve() {
        Arrays.fill(dp[0], -1);
        Arrays.fill(dp[1], -1);
        visit = new boolean[N + 1];
        if (dfs(1, true) > dfs(1, false)) {
            return 1;
        } else {
            return 0;
        }
 
    }
 
    public static int dfs(int n, boolean t) {
        int tt = t ? 1 : 0;
        if (dp[tt][n] != -1) {
            return dp[tt][n];
        }
        int sum = t ? W[n] : 0;
 
        visit[n] = true;
 
        if (t) {
            // that t is true is next node only pick false
            for (int next : edge[n]) {
                if (visit[next])
                    continue;
                p[n][tt].add(new Pair(next, 0));
                sum += dfs(next, false);
            }
        } else {
            // that t is false is next node pick true or false
            for (int next : edge[n]) {
                if (visit[next])
                    continue;
                if (dfs(next, false) > dfs(next, true)) {
                    p[n][tt].add(new Pair(next, 0));
                    sum += dfs(next, false);
                } else {
                    p[n][tt].add(new Pair(next, 1));
                    sum += dfs(next, true);
                }
 
            }
 
        }
 
        visit[n] = false;
        return dp[tt][n] = sum;
 
    }
}