[ BOJ 백준 2533번 - 사회망 서비스(SNS) ] 해설 및 코드

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

 

 

 

 

목적

인접한 두 개의 정점중 하나는 무조건 얼리 어답터여야 하며, 이 조건 하에 얼리 어답터의 최소 인원수를 구하자.

 

접근법

1. 동적 계획법으로 접근하자. 인접한 정점은 조건에 따라 얼리 어답터로 선정하여 최소 값을 도출해 낸다.

 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;i++)
using namespace std;
const int LEN=1e6+1;
int n,s[LEN][2];
bool vis[LEN]{};
vector<int> g[LEN];
 
int sol(int i,int k){
    int& ref=s[i][k];
    if(ref!=-1)return ref;
    
    vis[i]=true;
    ref=0;
    for(int j:g[i])if(!vis[j]){
        int tmp=sol(j,1);
        if(k==1)tmp=min(tmp,sol(j,0));
        ref+=tmp;
    }
    
    vis[i]=false;
    return ref+=k;
}
 
int main(){
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    cin>>n;
    f(i,1,n){
        int u,v;cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    memset(s, -1, sizeof(s));
    cout<<min(sol(1,0),sol(1,1));
    return 0;
}
 

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.