[백준] 1949 우수 마을 - DP + Tree DP(트리 다이나믹프로그래밍) JAVA

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

1949번: 우수 마을

코드설명

DP와 Tree DP 를 활용하는 문제입니다.

 

문제에 대한 설명입니다.

dp = new int[N+1][2]; //[N][0] : N번쨰 마을이 우수마을일경우의 최대 주민수 , [1] : N번째 마을이 우수마을이 아닐경우의 최대 주민수 를 의미합니다.

 

위의 로직을 활용해서 아래의 코드를 만듭니다. 주석을 확인하면 이해할 수 있습니다.

public static void simulate(int currentNode, int parent) {
    for(int i=0;i<graph.get(currentNode).size();i++) {
        int childNode = graph.get(currentNode).get(i);
        if(childNode != parent) { //만약 부모노드가 아니라면, 자식노드로 내려갑니다. 
            simulate(childNode, currentNode);
            dp[currentNode][0] += dp[childNode][1]; //현재노드가 우수마을이라면 자식노드는 우수마을이 아니어야만 한다.
            dp[currentNode][1] += Math.max(dp[childNode][0], dp[childNode][1]); //현재 노드가 우수마을이 아니라면, 자식노드가 우수마을이어도 되고, 아니어도 된다.
        }
    }
    dp[currentNode][0] += arr[currentNode]; //반드시 연관된 노드가 1개는 우수노드여야하므로 맨 아래 노드를 우수마을로 시작합니다.
}

문제에서 아마 가장 어렵게 느끼는점이, 어떻게 아래의 조건을 만족시키냐입니다.

1. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

'우수마을'로 선정되지 못한 마을이 적어도 하나의 우수마을과 인접시키기 위해 가장 아래 자식 노드를 우수노드로 반드시 상정하여 진행합니다.

이렇게할경우 우수마을이 아닌경우에는 아무 인원이 존재하지 않기에, 반드시 인접하도록 만들 수 있습니다.

코드

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

public class Main {
	
	public static int N, M, K;
	public static int answer;
	public static int[][] map;
	public static int[] arr;
	public static int[][] dp;
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	dp = new int[N+1][2];
    	arr = new int[N+1];
    	st = new StringTokenizer(br.readLine());
		for(int i=1;i<=N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
    	}
		
		for(int i=0;i<=N;i++) {
			graph.add(new ArrayList<Integer>());
		}
		
		for(int i=0;i<N-1;i++) {
			st = new StringTokenizer(br.readLine());
			int a= Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		
		simulate(1, 0);
		for(int i=1;i<=N;i++) {
			System.out.println("DP:"+dp[i][0] + " "+dp[i][1]);
		}
		System.out.println(Math.max(dp[1][0], dp[1][1]));
	}
	
	public static void simulate(int currentNode, int parent) {
		for(int i=0;i<graph.get(currentNode).size();i++) {
			int childNode = graph.get(currentNode).get(i);
			if(childNode != parent) { //만약 부모노드가 아니라면, 자식노드로 내려갑니다. 
				simulate(childNode, currentNode);
				dp[currentNode][0] += Math.max(dp[childNode][0], dp[childNode][1]);
				dp[currentNode][1] += dp[childNode][0];
			}
		}
		dp[currentNode][1] += arr[currentNode];
	}
	
}