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

문제

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

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

 

풀이 방법

해당 문제는 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++;
}