[알고리즘][15][백준_2533] - 사회망 서비스

 

---

 

이 문제에서 핵심이 되는 부분은

 

얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 이 아이디어를 받아들인다. 

이 부분이다.

 

이 말을 다르게 해석하면 결국 만약 자신이 일반인이라면 자신의 모든 친구들이 얼리어답터여야 함을 의미한다.

 

또한 만약 자신이 얼리어답터라면 자신의 친구가 일반인이던, 얼리어답터이던 중요하지 않다. 모두 가능하다.

 

정리하자면

 

얼리어답터 -> 얼리어답터 or 일반인
일반인 -> 얼리어답터

 

따라서 이것을 이용해 한정점에서 시작해 DFS로 순회하면서 위의 조건을 통해 최소의 얼리어답터 수를 구할 수 있을것이다.

 

---

 

만약 위와같은 트리로 전체적인 흐름을 파악해보자.

 

1번 정점부터 DFS를 수행한다고 할때 1번 정점에서 가능한 경우는 다음과 같이 두가지이다.

 

최종답은 두 경우중 얼리어답터가 더 적은 쪽이 될것이다.

 

[참고1,2] 1번이 얼리어 답터일때(좌측) 와 일반인일때(우측)

 

이후 3번 정점을 통해 dp를 어떻게 설계해야하는지 살펴보자.

 

a) 1번이 얼리어답터 일때

자신이 얼리어답터이므로 3번은 얼리어답터이거나(좌측 그림) 일반인이다(우측 그림).

 

2번도 마찬가지로 그 두경우 모두 가능하다.

 

[참고 3,4]

 

 

b) 1번이 일반인 일때

자신이 일반인이므로 3번은 반드시 얼리어답터여야한다.

 

2번도 마찬가지로 반드시 얼리어답터여야한다.

 

[참고 5]

 

중복 확인

이제 a,b 두 경우에서 각각 3번이 얼리어답터일때를 보자.

 

3번의 부모에서 부모가 얼리어답터건 일반인이건 상관없이 3번 이후로 (6,7,8)번의 선택에는 영향을 주지못한다.

 

따라서 두 경우 이후 최소가 되는 얼리어답터 수는 같을 것이고 이를 처리해주지않으면 중복호출로 시간복잡도가 증가한다.

 

따라서 해당 정점번호 + (얼리어답터 or 일반인여부) 를 가지고 메모이제이션을 해주면 중복을 해결 할 수 있다.

 

d[i][0] = i 번째 정점이 일반인 일때 이후 정점들의 최소 얼리어답터 수

d[i][1] = i 번째 정점이 얼리어답터 일때 이후 정점들의 최소 얼리어답터 수

 

코드 (C++)

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n;
vector<vector<int> > v;
int vt[1000002];
int dp[1000002][2];

int run(int now, int type){
    // now 정점을 type으로 했을때 최소값 리턴
    // type = 0 : 일반인 / 1 : 얼리어답터
    int next;
    int r1;
    int r2;
    int total = 0;
    int check = 0;

    if(dp[now][type] != -1){
        return dp[now][type];
    }

    for(int i=0;i<v[now].size();i++){ // 해당 정점에서 갈수있는 정점 모두 탐색
        next = v[now][i];
        r1 = 99999999;
        r2 = 99999999;
        if(vt[next] == -1){ // 다음노드가 아직 방문전이라면
            vt[next] = 1;
            if(type == 1){ // 현재 자신이 얼리어답터라면 다음 정점은 일반인이 될수있다.
                r1 = run(next,0);
            }
            r2 = run(next, 1); // 현재 자신이 일반인이던 얼리어답터건 다음 정점은 얼리어답터가 될수있다.
            vt[next] = -1;
        }
        if(!(r1 >= 99999999 && r2 >= 99999999)){
            if(r1 < r2){ // 다음 정점이 일반인, 얼리어답터 중에 더 적은 얼리어답터를 만든 경우를 계속 합산
                total = total + r1;
            }
            else{
                total = total + r2;
            }
        }
    }

    if(type == 1){ // 최종 최소치에 자신이 얼리어답터라면 본인도 포함
        total = total + 1;
    }
    dp[now][type] = total;
    return total;
}

int main(){
    int x,y;
    cin >> n;
    for(int i=0;i<=n;i++){
        v.push_back(vector<int>());
        vt[i] = -1;
        for(int j=0;j<2;j++){
            dp[i][j] = -1;
        }
    }
    for(int i=0;i<n-1;i++){
        cin >> x;
        cin >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    vt[1] = 1;
    int ans1, ans2;
    ans1 = run(1,0);
    for(int i=0;i<=n;i++){
        vt[i] = -1;
    }
    vt[1] = 1;
    ans2 = run(1,1);
    cout << min(ans1,ans2);
}