[백준 1949] 우수 마을 C++

1949번: 우수 마을

트리에서의 다이나믹 프로그래밍 입문 #2

[백준 15681] 트리와 쿼리 C++

이전 문제에서 아주 조금 개념이 추가된 트리 동적계획법 문제를 풀어보았다

 

만약 1번 마을이 우수 마을이라면 2번은 우수마을이 될 수 없다

2번이 우수마을이 아니므로 2번과 연결된 3, 6번 마을은 반드시 우수마을이 된다

 

1번 마을을 기본 루트로 지정!

 

이전 문제 트리와 쿼리와 다른점 1

---

dp배열 개념

// now번 마을이 0(일반 마을)일 때 now번 마을을 루트로 하는 서브트리의 우수 마을들 인구수의 최댓값

// now번 마을이 1(우수 마을)일 때 now번 마을을 루트로 하는 서브트리의 우수 마을들 인구수의 최댓값

int dp[10001][2];

---

dp[now][0] = 0;

dp[now][1] = CivilNum[now];

dfs를 돌면서 dp의 기본값을 세팅해 주어야 한다

now를 루트로 하는 서브트리에 속한 우수마들들의 인구수의 최댓 값이 dp[now][0]과 dp[now][1]에 들어가야 하기 때문에

초기의 dp[now][0]는 now가 루트인 서브트리에서 자신만 탐색한 상태이므로 0을 넣어주고

dp[now][1]에는 now가 루트인 서브트리에서 자신만 탐색한 상태이므로 현재 마을의 주민 수를 최댓값으로 넣어준다

(트리와 쿼리에서는 dp배열의 기본 값 자체를 1로 설정)

 

현재 노드가 우수마을이라면 다음에 탐색할 마을은 모두 일반 마을이어야 한다

따라서 dp[now][1] += dp[next][0]; 를 통해 dp[now][1]에는 next가 일반마을일 때 최댓값을 더해준다

 

만약 현재 노드가 일반 마을이라면?

무조건 dp[next][1]을 dp[now][0]에 더해줘야 할까?

아니다

예를 들어서 위와 같은 노드가 있고 1000이 기본노드(0)이고 Vertax의 숫자를 인구수라고 하자

이때 dp[1][0]은 얼마일까

dp[2][0]은 100이고 dp[2][1]은 1이다

그럼 dp[1][0]은 dp[1][0] + dp[2][0]을 해야 최댓값이 나온다

따라서 현재 노드가 일반 마을이라도 다음 노드는 일반 마을일 수 있다 (퐁당퐁당 형식이 아님)

dp[now][0] += max(dp[next][0], dp[next][1]);  // 최댓값을 찾기 때문에 조건 3번 만족

dp[now][1] += dp[next][0];

#include <bits/stdc++.h>
 
using namespace std;
 
int N;
// now번 마을이 0(일반 마을)일 때 now번 마을을 루트로 하는 서브트리의 우수 마을들 인구수의 최댓값
// now번 마을이 1(우수 마을)일 때 now번 마을을 루트로 하는 서브트리의 우수 마을들 인구수의 최댓값
int dp[10001][2];
int CivilNum[10001];
bool visited[10001];
vector<int> tree[10001];
 
void dfs(int now){
    visited[now] = true;
    
    dp[now][0] = 0;
    dp[now][1] = CivilNum[now];
    
    for(int i = 0; i < tree[now].size(); i++){
        int next = tree[now][i];
        if(visited[next]) continue;
        dfs(next);
        
        dp[now][0] += max(dp[next][0], dp[next][1]);
        dp[now][1] += dp[next][0];
    }
}
 
void input(){
    int u, v;
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> CivilNum[i];
    }
    for(int i = 1; i < N; i++){
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
}
 
int main(){
    input();
    dfs(1);
    cout << max(dp[1][0], dp[1][1]);
    return 0;
}

DFS, 양방향 트리, 2차원DP배열