백준 1949번 : 우수마을 - 트리 C++

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

1949번: 우수 마을

1. 문제설명

인접한 노드 두개가 우수마을이 되면 안된다.

그리고 자신이 우수마을이 아니라면 인접한 노드 중 적어도 하나가 우수마을이 되어야한다.

 

문제를 해결하기 위해

노드를 재귀적으로 탐색해야한다.

현재 노드가 우수마을인 경우와 우수마을이 아닌 경우를 나눈다.

 

그리고 현재 노드가 우수마을인 경우에는 다음 노드는 무조건 우수마을이면 안된다.

현재 노드가 우수마을이 아닌 경우에는 다음 노드는 우수마을이거나 우수마을이 아닐 수 있다.

 

이 때

현재 우수마을이 아닌데 다음 마을도 우수마을이 아닌 경우 문제가 생길 수 있다고 생각했다.

예를 들어 세개의 노드가 다 우수마을이 아닌 경우라면 문제의 조건에 맞지 않다.

하지만 다음 코드와 같이 재귀적으로 탐색하면서 최댓값을 계속 넘겨주다보면

모든 마을이 우수마을이 아닌 경우는 남지 않아서 괜찮다.

 

최댓값만 남기기 때문에 모든 마을이 우수마을이 아닌 경우는 살아남을 수 없다.

 

 

---

 

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;
#define MX 10001

int N, people[MX], dp[MX][2];
bool vis[MX];
vector<int> adj[MX];

void DFS(int node){
    dp[node][0] = 0;
    dp[node][1] = people[node];
    vis[node] = 1;

    for(int i=0; i<adj[node].size(); i++){
        int nx = adj[node][i];
        if(vis[nx]) continue;

        DFS(nx);
        dp[node][0] += max(dp[nx][0], dp[nx][1]);
        dp[node][1] += dp[nx][0];
    }
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N;
    for(int i=1; i<=N; i++){
        cin >> people[i];
    }

    for(int i=1; i<N; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    DFS(1);
    cout << max(dp[1][0], dp[1][1]) << '\n';
    return 0;
}