(백준) 스크루지 민호 2 _ 12978

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

 

🐢 설명

전형적인 트리 DP 문제이다.

 

먼저 N개의 정점이 있는데 간선이 N-1개라는 말이 있다면 트리를 의미하는건지 의심하면 되는데, 문제에서 보면

N - 1 개의 도로를 이용해 모든 도시들 사이에는 단 한개의 경로만이 존재하도록

이라는말이 있다. N-1개의 간선에 정점 간 단 한개의 경로만이 존재한다 하였으므로 트리구조임을 알 수 있다. 참고로 트리에서 루트 노드를 제외하고는 자신에게 들어오는 간선이 하나이므로 경로도 유일하다.

 

그러면 이제 트리임을 알았으므로 정점 아무거나 하나골라서 dfs를 통해 경찰서를 설치할지 말지 정해주면 된다.

경우의 수

• x정점에 경찰서를 설치할 경우
  • 자식 노드에는 경찰서를 설치해도 된다.
  • 자식 노드에는 경차를 설치 하지 않아도 된다.
• x정점에 경찰서를 설치하지 않은 경우
  • 자식 노드에는 경찰서가 설치 되어야 한다.

사실 x정점에 경찰서를 설치하지 않아도 자식에 설치를 안해도 되는 경우가 있다.

 

예를들어 x1정점에 설치가 안되어있고, x1정점에 여러 자식이 있을때 자식들이 말단 노드라면, x2에는 설치가 되어야만 한다.

하지만 x2에 xx5자식이 있고 xx5에 경찰서가 있다면 x2에 경찰서가 없어도된다.

근데 이러면 dp식 쓰기가 어려워 진다. 근데 이 경우는 말단 정점에 경찰서가 있고 해당 부모의부모에 경찰서가 없으며 다른 자식에 경찰서가 있는 경우에만 해당되는데 이 것은

NO - NO - YES == NO - YES - NO 구조 이므로 그냥 부모에 설치가 안됐으면 자식은 설치되어야 한다라고 해도 무방하다.

즉 어짜피 말단 노드에서 부모와의 Y - N / N - Y 차이뿐이므로 무조건 하나가 필요하다는데는 이견이 없다.

따라서 없으면 - 설치해야되고, 있으면 설치와 미설치중 이득인거 고르기 로 단순화가 가능하다.

🐢코드

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

public class Main {
	static int N;
	static ArrayList<Integer>[] adj;
	static boolean[] visited;
	static int[][] dp;
	static int YES = 1;
	static int NO = 0;

	public static void main(String[] args) throws Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		adj = new ArrayList[N + 1];
		visited = new boolean[N + 1];
		dp = new int[2][N + 1];
		for (int i = 0; i < N + 1; i++) {
			adj[i] = new ArrayList<>();
		}

		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());
			adj[u].add(v);
			adj[v].add(u);
		}

		dfs(1);
		System.out.println(Math.min(dp[YES][1], dp[NO][1]));
	}

	private static void dfs(int root) {
		visited[root] = true;
		dp[YES][root] = 1;

		for (Integer child : adj[root]) {
			if (visited[child]) continue;
			dfs(child);

			dp[YES][root] += Math.min(dp[YES][child], dp[NO][child]);
			dp[NO][root] += dp[YES][child];
		}
	}
}

🐢 마무리