백준 5934 (Visiting Cows) c++

문제

5934번: Visiting Cows

트리가 주어지면 트리의 최대 독립집합을 구하는 문제 입니다.

예를 들어 루트 노드로 'A'를 선택하면 {A, D}, {A, E}, {A, F} 가 독립 집합이 됩니다.

따라서 총 4개의 소를 방문할 수 있습니다.

반대로 루트 노드로 'A'를 선택하지 않고 'B'나 'C'를 선택하는 방법이 있습니다. 

그렇게 되면 또 'B'를 선택할것인지 선택 안할 것인지로 나뉘게되고 모든 노드 마다

이러한 과정이 반복됩니다.

따라서 DP 배열을 총 2가지로 나눌 수 있습니다.

DP[n][0] : n번쨰 노드를 선택하지 않고 독립집합으로 방문할 수 있는 노드의 갯수

DP[n][1] : n번째 노드를 선택하고 독립집합으로 방문할 수 있는 노드의 갯수

void dfs(ll x, ll par) {
    dp[x][1] = 1;
    for (auto nxt : v[x]) {
        if (nxt == par)continue;
        dfs(nxt, x);
        dp[x][0] += max(dp[nxt][0], dp[nxt][1]);
        dp[x][1] += dp[nxt][0];
    }
}

main 함수에서 dfs(1, 0)이 실행된 상태 입니다. 

첫번쨰 인자로는 현재 방문한 노드 번호가 들어가고 두번째 인자로는 현재 선택된 노드의 부모 노드가 들어갑니다.

따라서 지금 1번 노드 부터 살펴보는 것입니다.

2번째 줄을 보면 dp[x][1] = 1로 초기화 해줍니다. 왜냐하면 [1]은 자기 자신을 무조건 방문하기 때문입니다.

6번째 줄을 보면 dp[x][0] += max(dp[nxt][0], dp[nxt][1]) 이 됩니다. [0]은 자기 자신을 절대 방문하지 않기 때문에

자식 노드를 방문 할 수도 있고 안할 수 도 있습니다. 따라서 두개중에 더 큰값을 더해주는 것입니다.

---

전체 코드 입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll dp[50505][2];
vector<ll>v[50505];
ll n;
void dfs(ll x, ll par);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    for (int i = 1, a, b; i < n; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1, 0);
    
    cout << max(dp[1][0], dp[1][1]);
 
    return 0;
}
void dfs(ll x, ll par) {
    dp[x][1] = 1;
    for (auto nxt : v[x]) {
        if (nxt == par)continue;
        dfs(nxt, x);
        dp[x][0] += max(dp[nxt][0], dp[nxt][1]);
        dp[x][1] += dp[nxt][0];
    }
}