baekjoon 2533:사회망 서비스(SNS)

baekjoon 2533 사회망 서비스(SNS)

2533번 사회망 서비스(SNS)

접근

핵심은 tree를 만든 상황에서 이웃한 두 vertex 중 최소 하나는 색칠(얼리어답터)되어야 한다는 것이다.
그래서 이건 tree에서의 dp로 현재 vertex와 전 vertex가 색칠되었는지의 여부가 dp에 들어간다.

코드

//2533
#include <iostream>
#include <vector>
#include <array>
using namespace std;
void dfs(int i, vector<vector<int>>& adj, vector<vector<int>>& tree, vector<bool>& visited);
array<array<int, 2>, 1000000> cache;
int dp(int i, int prevStatus, vector<vector<int>>& tree);
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin >> n;
  vector<vector<int>> adj(n);
  vector<vector<int>> tree(n);
  vector<bool> visited(n, false);
  fill(cache.begin(), cache.end(), array<int, 2>{-1, -1});
  for(int i = 0; i < n-1; i++){
    int a, b; cin >> a >> b;
    adj[a-1].push_back(b-1);
    adj[b-1].push_back(a-1);
  }
  //make tree
  dfs(0, adj, tree, visited);
  // for(int i = 0; i < n; i++){
  //   for(int j = 0; j < tree[i].size(); j++){
  //     cout << tree[i][j]+1 << ' ';
  //   }
  //   cout << '\n';
  // }
  cout << dp(0, 1, tree);
  
  
  
  
  
  return 0;
}
void dfs(int i, vector<vector<int>>& adj, vector<vector<int>>& tree, vector<bool>& visited){
  visited[i] = true;
  for(int j = 0; j < adj[i].size(); j++){
    if(!visited[adj[i][j]]){
      tree[i].push_back(adj[i][j]);
      dfs(adj[i][j], adj, tree, visited);
    }
  }
}
int dp(int i, int prevStatus, vector<vector<int>>& tree){
  if(tree[i].size() == 0 && prevStatus == 0) return 1;
  if(tree[i].size() == 0 && prevStatus == 1) return 0;
  int& ret = cache[i][prevStatus];
  if(ret != -1) return ret;
  ret = 0;
  if(prevStatus == 0){
    //전에 색칠 안했으면 지금은 무조건 색칠
    ret = 1;
    for(int j = 0; j < tree[i].size(); j++){
      ret += dp(tree[i][j], 1, tree);
    }
  }
  else{
    //색칠 한다
    int color = 1;
    for(int j = 0; j < tree[i].size(); j++){
      color += dp(tree[i][j], 1, tree);
    }
    //안한다
    int noColor = 0;
    for(int j = 0; j < tree[i].size(); j++){
      noColor += dp(tree[i][j], 0, tree);
    }
    ret = min(color, noColor);
  }
  return ret;
}

배운 점

tree에서 dp를 사용하는 dp응용문제였다.