C++ 백준 2533 (사회망 서비스 SNS)

백준 2533 (사회망 서비스 SNS)

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

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

---

친구들간의 관계를 그래프로 표현해서 풀 수 있는 문제였다.

또한 중복되는 연산을 막기위해 DP를 사용하는데 설명에서 언급하겠다.

 

 

설명

---

문제 조건을 보면 얼리어답터가 아닌 사람들의 친구들은 무조건 얼리어답터여야 한다.

또한 얼리어답터가 아닌 사람들의 친구들은 얼리어답터이거나 아니어도 된다.

 

언뜻보면 이분그래프를 생각할 수 있지만, 얼리어답터가 아닌사람들의 친구들은 얼리어답터이거나 아니어도 되기 때문에 이분그래프가 항상 최적해를 보장해주지 않는다.

 

문제는 DFS로 풀 수 있다.

일단 아무나 한명 시작으로 잡는다.

 

그리고 현재 시작지점의 친구가 얼리어답터이거나 아닐때의 경우를 나누어 두번 재귀를 돌면 된다.

만약 현재 사람이 얼리어답터라면 주변 친구들이 얼리어답터여도 되고 아니어도 되기때문에 두번 돌지만, 만약 현재 사람이 얼리어답터가 아니라면 주변 친구들은 무조건 얼리어답터이기 때문에 한번만 재귀를 돌아도 된다.

 

만약 현재의 내가 얼리어답터여도 되고 아니어도 된다면 두번 재귀를 돈 후에 더 큰값을 리턴해주면 되는 것이다.

이때, 이미 방문했던 친구들은 최적해를 이미 한번 구해봤으므로 다시 접근할 필요가 없다.

 

이를 구현하기 위해 dynamic programming을 사용한다. 문제 분류를 보면 트리에서의 다이나믹 프로그래밍이라고 쓰여져 있는데 그냥 트리의 노드에 dp값을 저장한다고 보면 된다.

 

또한 문제에서 이 그래프는 무조건 트리형태의 구조를 가진다고 명시해줬기 때문에 사이클에 대해서 생각할 필요가 없다. 즉 한 노드에서 시작하면 무조건 한방향으로만 그래프 탐색이 진행된다.

 

예를 들어 dp[0][k]는 k번째 사람이 얼리어답터가 아니고 이 사람부터 한방향으로 진행했을 때 찾은 min값이다.

dp[1][k]는 k번째 사람이 얼리어답터일때 이 사람부터 한방향으로 진행했을 때 찾은 min값이다.

 

구현

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

vector <vector <int>> graph;
int early[1000001];
int dp[2][1000001];
int dfs(int curr, int prv){
    if(early[curr]==-1){
        int tmp=0;
        for(int i=0;i<graph[curr].size();i++){
            int dst = graph[curr][i];
            if(dst==prv) continue;
            if(dp[1][dst]==0){
                early[dst]=1;
                dp[1][dst] = dfs(dst, curr);
            }
            tmp+=dp[1][dst];
        }
        return tmp;
    }
    int tmp=1;
    for(int i=0;i<graph[curr].size();i++){
        int dst = graph[curr][i];
        if(dst==prv) continue;
        if(dp[1][dst]==0) {
            early[dst]=1;
            dp[1][dst]=dfs(dst, curr);
        }
        if(dp[0][dst]==0) {
            early[dst]=-1;
            dp[0][dst]=dfs(dst, curr);
        }
        tmp+=min(dp[0][dst],dp[1][dst]);
    }
    return tmp;
}

int main(void){
	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n,a,b;
    cin>>n;
    int start=0;
    graph.resize(n+1);
    memset(early, 0 ,sizeof(early));
    memset(dp, 0, sizeof(dp));
    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        if(start==0) start = a;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    early[start]=1;
    a = dfs(start, 0);
    early[start]=-1;
    b = dfs(start,0);
    cout<<min(a,b);
	return 0;
}