본문 바로가기

개발/알고리즘

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

문제

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

 

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

페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망

www.acmicpc.net

 

풀이 방법

해당 문제는 Tree DP 문제이다.

양방향 그래프를 다시 단방향 Tree로 만들어도 되지만 단방향으로 만들지 않아도 풀 수 있다.

 

1) 입력 데이터를 Tree 형태로 나타내기.

* 양방향으로 데이터를 담아주었다.

* 해당 데이터를 다시 단방향 Tree로 바꿔서 문제를 풀 수 있으나, 따로 단방향 Tree를 만들지는 않고 방문배열을 하나 만들어서 이미 방문한 정점은 다시 방문하지 않도록 처리하였다.

vector<int> adj[1000001];

void init(){
    cin >> n;
    for(int i = 0; i < n -1; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

 

 

2) DP Table 정의

경우의 수를 생각해보면 아래와 같다.

  • 현재의 정점이 얼리어답터임
    • 다음 정점이 얼리어답터임
    • 다음 정점이 얼리어답터가 아님
  • 현재의 정점이 얼리어답터가 아님
    • 다음 정점은 무조건 얼리어답터임

이를 다시 정의해보면,

DP[CurVertex][isEarlyAdaptor] = count 와 같이 표현할 수 있다.

  • DP[CurVertex][0] = count => CurVertex 는 얼리어답터가 아니고, CurVertex가 얼리어답터가 아닐때 최소 얼리어답터는 count개 입니다.
  • DP[CurVertex][1] = count => CurVertex 는 얼리어답터 이고, CurVertex가 얼리어답터 일 때 최소 얼리어답터는 count개 입니다.

이를 코드로 나타내면 다음과 같다.

int go(int vertex, int isEarlyAdaptor) {
    //메모이제이션
    int& ans = dp[vertex][isEarlyAdaptor];
    if(ans != -1) {
        return dp[vertex][isEarlyAdaptor];
    }

    //로직
    ans = 0;
    isVisit[vertex] = 1;
    
    //현재 정점이 얼리어답터 일 떄
    if(isEarlyAdaptor) {
        for(int i = 0; i < adj[vertex].size(); i++) {
            int nextVertex = adj[vertex][i];
            
            //이미 방문한 정점은 다시 계산하지 않는다.
            if(isVisit[nextVertex])
                continue;
                
            //다음 정점은 얼리어답터가 아니거나, 얼리어답터이다.
            ans += min(go(nextVertex, 0), go(nextVertex, 1));
            isVisit[nextVertex] = 0;
        }
        
        //해당 코드는 꼭 for block 이 끝난 다음에 해주어야 함.
        ans++;
    }
    //현재 정점이 얼리어답터가 아닐때
    else {
        for(int i = 0; i < adj[vertex].size(); i++) {
            int nextVertex = adj[vertex][i];
            
            //이미 방문한 정점은 다시 계산하지 않는다.
            if(isVisit[nextVertex])
                continue;

			//다음 정점은 무조건 얼리어답터이다.
            ans += go(nextVertex , 1);
            isVisit[nextVertex] = 0;
        }
    }

    return ans;
}

 

전체 코드

#include <iostream>
#include <vector>

using namespace std;

int n, u, v, isVisit[1000001], dp[1000001][2];
vector<int> adj[1000001];

void init(){
    cin >> n;
    for(int i = 0; i < n -1; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    //dp table -1 로 초기화
    fill(&dp[0][0], &dp[0][0] + 1000001 * 2, -1);
}

int go(int vertex, int isEarlyAdaptor) {
    //메모이제이션
    int& ans = dp[vertex][isEarlyAdaptor];
    if(ans != -1) {
        return dp[vertex][isEarlyAdaptor];
    }

    //로직
    ans = 0;
    isVisit[vertex] = 1;
    if(isEarlyAdaptor) {
        for(int i = 0; i < adj[vertex].size(); i++) {
            int nextVertex = adj[vertex][i];
            if(isVisit[nextVertex])
                continue;
                
            ans += min(go(nextVertex, 0), go(nextVertex, 1));
            isVisit[nextVertex] = 0;
        }
        ans++;
    } else {
        for(int i = 0; i < adj[vertex].size(); i++) {
            int nextVertex = adj[vertex][i];
            if(isVisit[nextVertex])
                continue;

            ans += go(nextVertex , 1);
            isVisit[nextVertex] = 0;
        }
    }

    return ans;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    init(); 

    cout << min(go(1, 0), go(1, 1));

	return 0;
}

 

문제풀면서 간과했던 부분

1. 양방향 그래프로 담아준 다음, 그래프를 탐색할때 단방향으로 탐색해야 한다는 점을 간과했음.

2. 얼리어답터 카운터 하는 부분 로직 실수

처음 코드를 아래와 같이 짰다.

현재 정점이 얼리어답터 일 경우에 min(go(nextVertex, 0), go(nextVertex, 1)) 를 구한다음 무조건 +1(내 자신이 얼리어답터이니까 +1)을 했다.  예제는 옳게 나왔는데, 문제 채점 결과는 틀렸습니다!..

if(isEarlyAdaptor) {
	for(int i = 0; i < adj[vertex].size(); i++) {
    	int nextVertex = adj[vertex][i];
        if(isVisit[nextVertex])
			continue;
                
        ans += min(go(nextVertex, 0), go(nextVertex, 1)) + 1;
        isVisit[nextVertex] = 0;
    }
}

어디서 틀렸을까 생각해보았는데,

만약 leaf Node가 얼리어답터 일 경우 +1이 되어야하는데

위와 같은 코드는 for block 자체를 수행하지 않기때문에 +1이 되지 않음을 알 수 있었다.

 

해당 부분을 아래와 같이 수정해주니 정답!

if(isEarlyAdaptor) {
	for(int i = 0; i < adj[vertex].size(); i++) {
    	int nextVertex = adj[vertex][i];
        if(isVisit[nextVertex])
			continue;
                
        ans += min(go(nextVertex, 0), go(nextVertex, 1));
        isVisit[nextVertex] = 0;
    }
    ans++;
}