[백준 1949번] [동적 계획법] 우수 마을

상당히 어려운 문제이다.

DP의 트리에서의 이용이라고 할 수 있겠다.

푸는 느낌을 잘 기억해두도록 하자.

접근 방법

1. 각 Root가 진행될 수 있는 나아갈 수 있는 방향은 우수방향으로 선택되거나 선택되지 않는 2가지 방향밖에 없다.

2. 그런데, 문제 조건을 보면 각 연결된 노드끼리 동시에 우수마을이 될 수 없으므로 각 root가 진행될 수 있는 방향은 독립적인 것이 아닌 종속적이다.

3. 이때 종속시키는 기준이 필요하므로 아래를 기준으로 위를 채우는 방향으로 진행하면 된다.

# Case 1 :  Root를 선택하는 방향
이 케이스의 경우는 Sub node가 무조건 선택되지 않으면 된다.

# Case 2 : Root를 선택하지 않는 방향
이 케이스의 경우는 Sub node가 선택되거나 선택되지 않는 것 중 최댓값을 고르면 된다.

즉, 각 case에 대하여 필요한 정보는 하부 sub Node가 선택되거나 선택되지 않았을 때의 최댓값이다.
따라서 이를 DP로 잡으면 된다.(그러면 불필요한 계산을 줄여나가면서 완전 탐색할 수 있게 된다.)
추가적으로 트리를 타고 내려가면서 밑바닥에서 계산을 시작해야하므로 DFS, BFS 모두 가능하다.
(만약 DFS를 이용할 경우 Recursion, BFS를 이용할 경우 Queue를 이용해주면 된다.)

이 문제에서 선택되냐, 선택되지 않냐를 기준으로 2가지 데이터가 필요하므로 DP를 2차원배열로 잡은 것이다.

 

다만, 처음에 길을 저장할 때 2차원 배열로 잡아서 총 10000 x 10000의 데이터를 잡아먹어서 메모리 초과가 나왔다.

그래서 vector container를 활용하여 필요한 부분만 저장하여 recursion으로 순차탐색함으로써 메모리 절약을 하였다.

 

해당하는 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

vector<int> road[10001];
int visited[10001];
int citizen_num[10001];
int dp[10001][2]; // i번쨰 인덱스가 선택되었을 떄 : 1, 선택되지 않았을 때 0
                  // 해당 i번째를 기준으로 시민들 수와 합의 최댓값

int civil_num;

void dfs(int node){
    if(visited[node] != 0) return;
    else{
        visited[node] = 1; // 방문 처리
        int zero_check = 0;
        int one_check = 0;
        for(int i = 0; i < road[node].size(); i++){
            if(visited[road[node][i]] == 0){
                dfs(road[node][i]);
                one_check += dp[road[node][i]][0];
                zero_check += max(dp[road[node][i]][0], dp[road[node][i]][1]);
            }
        }
        dp[node][0] = zero_check;
        dp[node][1] = one_check + citizen_num[node];
        return;
    }
}

int main(void){
    cin >> civil_num;
    
    for(int i = 1; i <= civil_num; i++){
        int temp;
        cin >> temp;
        citizen_num[i] = temp;
    }// Citizen store

    memset(road, 0, sizeof(road)); // Initializa road memory to 0

    for(int i = 1; i <= civil_num - 1; i++){
        int civil1, civil2;
        cin >> civil1 >> civil2;
        road[civil1].push_back(civil2);
        road[civil2].push_back(civil1);
    }

    memset(dp, 0, sizeof(dp));

    // 위에가 선택되면 >> 아래는 선택이 안됨(DFS로 처리하면됨 아래서부터)
    // 미선택을 0, 선택을 1로 취급하자.
    dfs(1);

    cout <<max(dp[1][0], dp[1][1]) << "\n"; // 최댓값 출력
    return 0;
}

무난하게 통과하였다.