[백준OJ] 12978번 스크루지 민호 2

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

12978번: 스크루지 민호 2

---

 

-풀이-

트리DP를 이용했다. dp[i][j]=k 라 할때,  i번째 노드의 상태가 j일때( j==0 경찰서x / j==1 경찰서 o) 자식노드들과 자신을 포함하여 지어야할 경찰서의 최소개수가 k개라는것이다.

 

먼저 현재 노드에서 경찰서를 짓는다면, 자식노드들은 경찰서를 지어도되고, 안지어도된다.

만약 현재 노드에서 경찰서를 짓지 않는다면? 자식노드들은 무조건 경찰서를 지어야 한다.

이 두가지 경우를 이용하여 모든 경우의 수를 구해주는데, 매번 갱신을 할때마다 자식들을 하나하나 탐색을 한다면, 시간초과가 나므로, dp를 이용해서 시간복잡도를 줄여주었다.

 

-코드-

#include <iostream>
#include<algorithm>
#include<vector>
#define MAX 987654321
using namespace std;

vector<int> maze[100001];
int n;
int dp[100001][2];

int dfs(int now, int parent, int isPolice) {
	if (dp[now][isPolice] != MAX) {
		return dp[now][isPolice];
	}

	int police = 0;
	if (isPolice) police++;//자기자신노드에 경찰서가 있으면 개수+1

	for (int next : maze[now]) {
		if (next != parent) {
			if (!isPolice) {
				//부모에 경찰서가 없으면, 자식은 무조건 경찰서가 있어야함.
				police += dfs(next, now, 1);
			}
			else {
				//부모에 경찰서가 있으면, 자식은 있는거 or 없는것 중 더 작은쪽을 택하면됨
				police += min(dfs(next, now, 1), dfs(next, now, 0));
			}
		}
	}
	//해당 경우의 최솟값을 저장
	return dp[now][isPolice] = police;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		maze[a].push_back(b);
		maze[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) {
		dp[i][0] = dp[i][1] = MAX;
	}

	cout << min(dfs(1, 0, 0), dfs(1, 0, 1));

	return 0;
}