백준 2533

문제

---

깊이 우선 탐색(DFS)으로 DP를 계산

DP에는 해당 노드까지의 최소 얼리어답터 수를 저장한다.

그러면 각각의 노드에서는, 무조건 아래의 두 경우 중 하나이다.

1) 해당 노드가 얼리어답터일 경우

• 무조건 자식 노드가 얼리어답터

2) 해당 노드가 얼리어답터가 아닐 경우

• 자식노드가 얼리어답터일 수도 아닐 수도

• 두 경우 중 얼리어답터 수가 더 적은 쪽 선택
  

dp[i][j] : i번 노드가 루트 노드일때 최소 인원 수

• j == 0 --> i번 노드가 얼리어탑터일 때

• j == 1 --> i번 노드가 얼리어탑터 아닐 때

---

마지막으로 임의의 노드는 얼리어답터 집합에 속할 수도 있고, 아닐 수도 있다.

편의를 위해 1번 노드를 루트 노드로 생각하면

dp[1][0]과 dp[1][1] 중 더 작은 쪽이 정답

---

Code

package test;

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

public class P2533 {

	static boolean[] visited;
	static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
	/*
	dp : 해당 지점까지의 얼라어답터 수
	 dp[i][j] : i번 노드일때  
	 j == 0 --> i번 노드가 얼리어답터일 경우 
	 j == 1 --> i번 노드가 얼리어답터 아닐 경우
	 */
	static int[][] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int N = Integer.parseInt(br.readLine());

		visited = new boolean[N + 1];
		dp = new int[N + 1][2];
		for(int i = 0; i <= N; i++) {
			list.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());
			list.get(a).add(b);
			list.get(b).add(a);
		}
		dfs(1);
		
		bw.write(String.valueOf(Math.min(dp[1][0], dp[1][1])));
	
		br.close();
		bw.flush();
		bw.close();
	}
	private static void dfs(int num) {
		visited[num] = true;
		dp[num][0] = 0;
		dp[num][1] = 1;
		
		for(int child : list.get(num)) {
			if(!visited[child]) {
				dfs(child);
				/*
				 1) 해당 노드가 얼리어답터가 아닐 때
				 --> 자식 노드가 얼리어답터
				 */
				dp[num][0] += dp[child][1]; 
				/*
				 2) 해당 노드가 얼리어답터일 때
				 --> 자식 노드가 얼리어답터일 때와 아닐 때 중 
				 	총 얼리어답터 인원이 적을 쪽을 선택
				 */
				dp[num][1] += Math.min(dp[child][0], dp[child][1]);
			}
		}
	}
}

---

참고 : https://maivve.tistory.com/322