[2213번] 트리의 독립집합

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 트리

2. Dynamic Programming

이 문제는 전형적인 트리 DP 문제이다.

1. 현재 노드를 사용한다면 다음 노드는 사용하지 않고, 

2. 현재 노드를 사용하지 않는다면 다음 노드를 사용하거나 하지 않을때 중 최댓값을 찾아주면 된다.

이 과정을 재귀를 이용하여 문제를 해결하고 그때마다의 결과를 dp에 저장하여 메모이제이션을 해준다.

두번째로 이문제는 그렇게 정답을 찾아냈다면 추적까지 해보라는 문제이다.

추적을 할 때는 만약 현재 노드를 사용하고 있다면 다음 노드는 무조건 사용되지 않고 있을 것이고,

현재 노드가 사용되고 있지 않다면, 

이때는 dp값을 확인하여 다음 값을 사용할 때 dp값이 더 높다면 다음값을 사용해주고 

그렇지 않다면 다음 값을 사용하지 않는 방식으로 추적을 해나간다.

이 문제를 풀며 상당히 많이 틀렸는데, 조심해야 할 점을 말해보자면

   if(chk)

       ret = value[here];

    

   else ret = 0;

   for (auto next : vc[here])

   {

      if (next == prev)

         continue;

      if (chk)

         ret += dfs(here, next, 0);

      else

         ret += max(dfs(here, next, 0), dfs(here, next, 1));

   }

위와 아래 코드는 완전 다름을 알고 있어야 한다.

   else ret = 0;

   for (auto next : vc[here])

   {

      if (next == prev)

         continue;

      if (chk)

      {  

         ret = value[here];    

         ret += dfs(here, next, 0);

      }

      else

         ret += max(dfs(here, next, 0), dfs(here, next, 1));

   }

첫번째 코드와 가장 결정적인 차이는 if(next == prev)에 걸리게 되면 ret = value[here]를 받지 못하는 상황이 나오기 때문에

무조건 전처리를 해두는 것이 맞다.

유사문제로 

[1949번] 우수 마을 :: http://www.crocus.co.kr/636을 풀어보자.

 

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <memory.h>
 
using namespace std;
 
int value[10002];
int dp[10002][2];
vector<int> vc[10002];
vector<int> ans;
 
int dfs(int prev, int here, bool chk)
{
   int &ret = dp[here][chk];
 
   if (ret != -1)
      return ret;
 
   if(chk)
       ret = value[here];
    
   else ret = 0;
 
   for (auto next : vc[here])
   {
      if (next == prev)
         continue;
 
      if (chk)
         ret += dfs(here, next, 0);
 
      else
         ret += max(dfs(here, next, 0), dfs(here, next, 1));
   }
 
   return ret;
}
 
void trace(int prev, int here, bool chk)
{
   if (chk)
   {
      ans.push_back(here);
      for (auto next : vc[here])
      {
         if (next == prev)
            continue;
 
         trace(here, next, 0);
      }
   }
 
   else
   {
      for (auto next : vc[here])
      {
         if (next == prev)
            continue;
 
         if (dp[next][1] >= dp[next][0])
            trace(here, next, 1);
         else
            trace(here, next, 0);
      }
   }
}
int main()
{
   memset(dp, -1, sizeof(dp));
 
   int n;
   scanf("%d", &n);
 
   for (int i = 1; i <= n; i++)
      scanf("%d", &value[i]);
 
   for (int i = 0; i < n - 1; i++)
   {
      int from, to;
      scanf("%d %d", &from, &to);
 
      vc[from].push_back(to);
      vc[to].push_back(from);
   }
 
   int a = dfs(-1, 1, 0);
   int b = dfs(-1, 1, 1);
 
   if (a >= b)
      trace(-1, 1, 0);
   else
      trace(-1, 1, 1);
 
   sort(ans.begin(), ans.end());
 
   printf("%d\n", max(a, b));
   for (auto i : ans)
      printf("%d ", i);
 
   return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>