[Algorithm]Baekjoon 2213번 : 트리의 독립집합

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

2213번: 트리의 독립집합

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
 
int n;
int weights[10001] = { 0 };
vector<vector<int>> graph(10001);
int dp[10001][2] = { 0 };
bool visited[10001] = { false };
vector<int> route;
 
void DFS(int node)
{
    visited[node] = true;
 
    dp[node][0] = 0;
    dp[node][1] = weights[node];
 
    for (int i = 0; i < graph[node].size(); ++i)
    {
        int nextNode = graph[node][i];
 
        if (visited[nextNode]) continue;
 
        DFS(nextNode);
 
        dp[node][0] += max(dp[nextNode][0], dp[nextNode][1]);
        dp[node][1] += dp[nextNode][0];
    }
 
    visited[node] = false;
}
 
void RouteNavigation(int node, bool isSelected)
{
    visited[node] = true;
 
    if (isSelected)
    {
        route.push_back(node);
    }
 
    for (int i = 0; i < graph[node].size(); ++i)
    {
        int nextNode = graph[node][i];
 
        if (visited[nextNode]) continue;
 
        if (isSelected)
        {
            RouteNavigation(nextNode, false);
        }
        else
        {
            if (dp[nextNode][0] > dp[nextNode][1])
            {
                RouteNavigation(nextNode, false);
            }
            else
            {
                RouteNavigation(nextNode, true);
            }
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> weights[i];
    }
 
    for (int i = 0; i < n - 1; ++i)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    DFS(1);
 
    cout << max(dp[1][0], dp[1][1]) << endl;
 
    if (dp[1][0] > dp[1][1])
    {
        RouteNavigation(1, 0);
    }
    else
    {
        RouteNavigation(1, 1);
    }
 
    sort(route.begin(), route.end());
 
    for (int i = 0; i < route.size(); ++i)
    {
        printf("%d ", route[i]);
    }
}

 

이전에 풀었던 우수마을 문제에서 경로까지 알아내야하는 문제이다.

 

일단 나는 과정을 크게 두가지로 나눴다.

 

1. 우수마을문제처럼 각 정점을 선택했을 때와 안선택했을때의 최대값을 dp테이블에 업데이트.

      -> 우수마을문제랑 똑같은 코드다.

 

2. 그다음 경로를 알아내기 위해 1번노드부터 또 탐색.

      -> 각 정점마다 선택,안선택의 최대값을 알고있으니, 그거에 맞춰서 자식노드를 탐색하면 된다.

           필요한만큼만 진행되기 때문에 최대 n번의 탐색으로 끝난다.

 

기존의 우수마을문제에 대해 dp테이블을 업데이트하는 방식을 이해했다면 2번도 쉽게 이해할 수 있다.

현재정점 선택여부에 따라 자식정점을 선택하고 넘어갈지 안넘어갈지 딱 정해지기 때문에 n번으로 가능하다.

 

예를들어 현재정점을 선택했다면, 자식정점은 무조건 선택하면 안된다.

그렇기 때문에 현재정점을 나중에 출력할 경로컨테이너에 넣어주고 해당자식정점은 선택안했다는 체크와 함께 자식정점으로의 탐색을 이어가면 된다.

 

그러나 현재정점을 선택안했다면, 자식정점을 선택 or 안선택해도 되기 때문에 두 값 중 큰값을 따라간다.

즉, 자식정점을 안선택한 값이 더 크다면 (dp[자식정점][0] > dp[자식정점][1] 이라면), 마찬가지로 선택안했다는 표시와 함께 자식정점으로의 탐색을 이어가면 된다.

만약 자식정점을 선택한 값이 더 크다면, 선택했다는 표시와 함께 자식정점으로의 탐색을 이어가면 된다.

 

그리고 반드시 경로를 출력할 때는 오름차순으로 출력해야 한다. 하마터면 시간날릴뻔했는데 다행히 질문하기게시판에 누가 경고를 남겨줘서 시간을 아낄 수 있었다.

 

그리고 DFS함수에서 함수마지막에 visited[node] = false;는 없어도 dp테이블은 전부 정상적으로 업데이트 되지만, 해당 visited를 RouteNavigation함수에서 또 쓰기위해 false값 대입코드를 추가해놨다.