사회 연결망 서비스(SNS)

Problem link: https://www.acmicpc.net/problem/2533

처음에 떠올린 솔루션은 재귀, 이내 중복으로 계산하는 경우가 많은 것을 떠올리고 DP로 전환하였다.

점화식 설계는 아래와 같다.

T(root, is_ea): root번 정점을 루트로하는 서브트리에서, root번 정점이 얼리어답터인지의 여부가 is_ea일 때, 필요한 얼리어답터의 최소 수

• T(root, true): sum(min(T(child, 1), T(child, 0)))
  • 기본적으로 모든 자식 서브트리들에 대해서 문제를 풀어주고 합을 구해주는데,
  • root번 정점이 이미 얼리어답터이므로 자식노드들은 얼리어답터일 수도, 아닐 수도 있다.
  • 따라서, 둘 중 작은 값으로 구해서 더해준다.

• T(root, false): sum(T(child, 1))
  • 기본적으로 모든 자식 서브트리들에 대해서 문제를 풀어주고 합을 구해주는데,
  • root번 정점이 얼리어답터가 아니므로 반드시 자식노드들은 얼리어답터이어야 한다.

이 때, 사실 주어지는 입력은 그래프이므로 미리 DFS트리를 구성해주어야 한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

static const size_t kMaxN = 1000000;

size_t N;
vector<size_t> SNS[kMaxN];

bool VISIT[kMaxN];
vector<size_t> TREE[kMaxN];

size_t CACHE[kMaxN][2];

void Dfs(const size_t root)
{
  VISIT[root] = true;

  for (const auto& f : SNS[root])
  {
    if (!VISIT[f])
    {
      TREE[root].push_back(f);
      Dfs(f);
    }
  }
}

size_t Solve(const size_t root, const bool is_early_adapter)
{
  if (root >= N)
  {
    return kMaxN + 1;
  }

  size_t& ret = CACHE[root][is_early_adapter];

  if (ret != kMaxN + 1)
  {
    return ret;
  }

  if (is_early_adapter == 0)
  {
    ret = 0;
    for (const auto& f : TREE[root])
    {
      ret += Solve(f, 1);
    }
  }
  else
  {
    ret = 1;
    for (const auto& f : TREE[root])
    {
      ret += min(Solve(f, 0), Solve(f, 1));
    }
  }

  return ret;
}

int main(void)
{
  // For faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read input
  cin >> N;

  for (size_t it = 0; it + 1 < N; ++it)
  {
    size_t A, B;
    cin >> A >> B;
    SNS[A - 1].push_back(B - 1);
    SNS[B - 1].push_back(A - 1);
  }

  // Initialize
  for (size_t it = 0; it < N; ++it)
  {
    VISIT[it] = false;
    CACHE[it][0] = kMaxN + 1;
    CACHE[it][1] = kMaxN + 1;
  }

  Dfs(0);

  // Solve
  cout << min(Solve(0, 0), Solve(0, 1)) << "\n";

  return 0;
}