[BOJ알고리즘, C++]#1949_우수마을, 트리 DP

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. 트리

https://webddevys.tistory.com/287

[자료구조]#5_트리

트리 자료구조는 그래프의 한 종류로, 1:N 관계의 계층구조를 갖는 비 선형 자료구조입니다. 만약, 트리 노드의 개수가 N이라면, 간선의 개수는 N-1이며, 비순환 구조입니다. 

 

2. DP

https://webddevys.tistory.com/311

[알고리즘]#5_동적 계획법

동적 계획법은 최적화 기법으로 입력 크기에 따라 중복되는 하위 문제를 재귀적으로 해결하고, 여기서 얻은 결과 값을 기억하는 것으로 중복 계산을 방지해 알고리즘의 최적화를 수행합니다. 

 

3. 트리 DP 유형 문제, 루트 -> 단말 노드 순서? 단말 노드 -> 루트 순서?

1. 먼저, 주어진 입력 정보를 통해 트리를 구성합니다.
2. DFS 활용 DP를 구현합니다. 이때, 각 마을이 '우수 마을'로 선택 되는 한 가지 경우와 '우수 마을'로 선택되지 않은 한 가지 경우, 총 두 가지 경우에 대하여 DP를 수행해야합니다. 
3. 먼저, 결과 값은 '우수 마을'의 주민 수의 총합으로 하나의 결과 값이 필요합니다. 트리 자료구조에서 단말 노드는 1개 이상이지만, 루트 노드는 유일합니다. 따라서, 임의의 정점을 시작 정점 혹은 루트 노드로 설정하고, DFS 활용 DP를 수행하도록 설계합니다.
4.  첫 번째 경우, 어떤 마을이 '우수 마을'일 경우, 인접한 다른 모든 마을은 '우수 마을'일 수 없습니다. 따라서, 인접 정점을 순회하며 DFS를 수행하기 전에, 현재 마을이 우수 마을일 경우의 주민의 수에 인접 마을들이 '우수 마을'이 아닐 경우의 주민의 수를 더해줍니다.
5. 두 번째 경우, 어떤 마을이 '우수 마을'이 아닐 경우, 인접한 다른 모든 마을은 '우수 마을'일 수 도 있고, '우수 마을'이 아닐 수 도 있습니다. 따라서, 현재 마을이 우수 마을이 아닐 경우의 주민 수에 인접 마을들이 '우수 마을'이 아닐 경우와 '우수 마을'일 경우의 주민의 수 중 더 큰 수를 더해줍니다.

 

---

 

#3. 코드

/*
    @문제 :  1~N번마을과 N-1개의 방향성 없는 길로 이루어진 트리 구조의 마을, A-B 직접적인 연결 -> 인접한 마을!

            1. 우수 마을로 선정된 마을의 주민의 수는 최대가 되어야한다.
            2. 두 마을이 인접하다면, 두 마을 모두 '우수 마을'이 될 수 없다. 
            3. 우수마을로 선정되지 못한 마을은 항상 '우수 마을'로 선정된 마을과 인접해야한다.

    @설명
            1. DP 활용
            2. 현재 노드에 대하여 두 가지 결과 값 저장 : 현재 노드가 '우수 마을'일 경우 + 현재 노드가 '우수 마을'이 아닐 경우
            3. 먼저, 현재 노드가 '우수 마을'일 경우, 인접 노드는 모두 '우수 마을'이 아니다!
            4. 다음, 현재 노드가 '우수 마을'이 아닐 경우, 인접 노드가 '우수 마을'일 경우와 '우수 마을'이 아닐 경우의 결과 값 중 최대 값을 전달해준다.
*/

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

#define MAX 10001

int N;
int People[MAX];
int dp[MAX][2];
vector<vector<int>> tree(MAX);
vector<bool> visited;

void dfs(int node)
{
    visited[node] = true;
    dp[node][0] = 0;
    dp[node][1] = People[node];

    for(const auto neighbor : tree[node])
    {
        if(visited[neighbor]) continue;

        dfs(neighbor);

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    visited.resize(N+1, false);

    // 주민의 수
    for(int i=1; i<=N; ++i)
        cin >> People[i];

    // 마을 사이의 길 정보(양방향)
    for(int i=0; i<N-1; ++i)
    {
        int A, B;
        cin >> A >> B;

        tree[A].push_back(B);
        tree[B].push_back(A);
    }

    dfs(1);

    cout << max(dp[1][0], dp[1][1]);

    return 0;
}

 

---