boj 12978 스크루지 민호 2

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

12978번: 스크루지 민호 2

오랜만에 알고리즘 포스팅입니다.

 

N개의 도시와 N - 1개의 도로인 것으로 보아 트리 문제인 것으로 파악할 수 있으며,

최소 갯수의 경찰서를 세워 모든 도시, 도로를 감시해야 합니다.

 

모든 도시들 대상으로 경찰서를 세우는 경우, 세우지 않는 경우를 모두 구한다면 시간초과가 발생할 것입니다.

따라서 dp를 추가하여 treedp로 접근합니다.

 

dp[v][flag]: 현재 도시가 v이고, 상태가 flag일 때 세워야할 경찰서의 최소 갯수

여기서 상태란, 현재 도시에 경찰서를 세울지 결정하는 변수입니다.

flag = 1 일 때, 해당 도시에 경찰서를 세우고,

flag = 0 일 때, 해당 도시에 경찰서를 세우지 않는 경우입니다.

 

이러면 다음 도시부터는 계산하기 수월해집니다.

현재 도시에서 경찰서를 세웠더라면 다음 도시에서는 경찰서를 세워도 되고, 세우지 않아도 됩니다. 즉, 두 경우 모두 확인합니다.

현재 도시에서 경찰서를 세우지 않았더라면 다음 도시에서는 경찰서를 무조건 세워야 합니다. 즉, 하나의 경우만 확인합니다.

마지막으로 해당 경우의 합의 최솟값을 출력합니다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX 100001
using namespace std;
 
vector<int> graph[MAX];
int dp[MAX][2];
int N;
 
int dfs(int v, int pre, int flag) {
    int& ret = dp[v][flag];
    if (ret != -1) return ret;
    ret = flag;
 
    for (auto next : graph[v]) {
        if (pre == next) continue;
        if (flag) {
            ret += min(dfs(next, v, 1), dfs(next, v, 0));
        }
        else {
            ret += dfs(next, v, 1);
        }
    }
 
    return ret;
}
 
void func() {
    memset(dp, -1, sizeof(dp));
    cout << min(dfs(1, 0, 1), dfs(1, 0, 0)) << '\n';
}
 
void input() {
    int u, v;
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}