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

🔗 문제

1949번: 우수 마을

1949번: 우수 마을

 

✍️풀이

 

문제를 읽어보면 트리 구조의 마을에 정점에 가중치가 주어진다.

마을은 인접한 마을끼리 우수마을이 될 수 없으며, 우수 마을이 아닌 곳은 적어도 하나의 우수 마을과 인접해야 한다.

 

 

어떤 노드를 선택했을 때, 그 마을을 우수 마을로 하느냐 하지 않느냐에 따라서 어떤 합이 나올지 몰라 계산이 필요한 식이다. 그냥 여기서 dp가 떠올랐다. 하지만 .. 어떻게 문제를 풀지는 감이 잡히지 않아서 인터넷의 도움을 받았다. 😀..

 

🔗 참고 블로그 : https://loosie.tistory.com/226

 

 

N개의 정점이 있다는 사실과 우수 마을인지 아닌지로 결과가 달라지는 값을 저장하기 위한 배열이 필요하다.

int dp[2][MAX_N] = {0, };

// dp[0][x] x번째 마열이 우수 마을이 아닐 때 가장 큰 우수 마을 주민 합
// dp[1][x] x번째 마을이 우수 마을일 때 가장 큰 우수 마을 주민 합

 

 

일단 트리구조라는 점을 이용해서 세개의 노드를 생각해보자.

 

만약 1번 노드가 우수 마을로 선정된다면 하위 노드인 2와 3은 우수마을에 선정되지 못한다.

dp[1][1] = dp[0][2] + dp[0][3]

dp[1][parent] = cost[parent];

for(const auto& child : parent)
{
	dp[1][parent] += dp[0][child];
}

 

 

하지만 노드 1이 우수 마을이 아니라면 아래 3가지 경우 중 가장 큰 값이 정답이 된다.

 

각 자식노드마다 우수마을이거나 아니거나 어떤게 더 큰 큰 값인지 재서 값을 더해야 한다.

for(const auto& child : parent)
{
	dp[0][parent] += std::max(dp[1][child], dp[0][child]);
}

 

 

 

 

이걸 dfs로 표현해보자~~

void dfs(const int idx, const int parent)
{
    dp[0][idx] = 0;
    dp[1][idx] = cost[idx];

    for (const auto& i : tree[idx])
    {
        if (i == parent) continue; // 무한 반복을 벗어나기 위한 체크

        dfs(i, idx); // bottom-up하기 위해서 자식 노드 값을 먼저 채운다. 
        dp[0][idx] += std::max(dp[1][i], dp[0][i]);
        dp[1][idx] += dp[0][i];
    }
}

 

💾  소스

#include <iostream>
#include <vector>
#include <cmath>

int N, answer = 0;
std::vector<int> cost;
std::vector<std::vector<int>> tree;
std::vector<std::vector<int>> dp;

void dfs(const int idx, const int parent)
{
    dp[0][idx] = 0;
    dp[1][idx] = cost[idx];

    for (const auto& i : tree[idx])
    {
        if (i == parent) continue;

        dfs(i, idx);
        dp[0][idx] += std::max(dp[1][i], dp[0][i]);
        dp[1][idx] += dp[0][i];
    }
}

int main()
{

    std::cin >> N;
    cost.resize(N + 1);
    tree.resize(N + 1);
    dp.resize(2, std::vector<int>(N + 1, 0));

    for (int i = 1; i <= N; ++i)
        std::cin >> cost[i];

    int a, b, start = 1;
    for (int i = 0; i < N - 1; ++i)
    {
        std::cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    dfs(start, 0);

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

    return 0;
}