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

문제 링크 => 2533번: 사회망 서비스(SNS) (acmicpc.net)

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

---

다이나믹 프로그래밍 문제이다.

 

얼리 아답터인 경우와 얼리 아답터가 아닌 경우를 나누기 위해 2차원 배열 memo[1000001][2] 를 설정하였다.

 

얼리 아답터인 경우 (memo[x][1]) => memo[x][1] += min(dp(next, 1, x) + 1, dp(next, 0, x)) (그 다음 노드가 얼리 아답터인 경우와 얼리 아답터가 아닌 경우에 대해 고려해본 결과중 최솟값을 결정함)

 

얼리 아답터가 아닌 경우 (memo[x][0]) =>  memo[x][0] += dp(next, 1, x) + 1 (그 다음 노드는 항상 얼리 아답터임을 알 수 있음)

 

이때 dp의 parameter 중에 x, c, mx 에서 mx는 x의 parent node 이며 c는 얼리 아답터인 경우와 아닌 경우를 판단하도록 한다.

 

그리고 함수를 처음에 호출할 때 부모노드가 없는, 즉 자식노드가 1개만 존재하는 경우의 노드 x를 찾아서 dp(x, 0, -1) 를 호출해주도록 하자. (이때의 x 노드는 얼리 아답터가 아님이 분명하고 부모노드는 알 수 없으므로 -1으로 임의로 설정)

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define MOD 1000000009

using namespace std;

vector<int> v[1000001];
int memo[1000001][2];
bool check[1000001][2];
int n;

int dp(int x, int c, int mx) {  // mx : x's parent node
	if (check[x][c]) return memo[x][c];
	check[x][c] = true;

	for (int i = 0; i < v[x].size(); i++) {
		if (v[x][i] == mx) continue;
		if (c == 0) memo[x][c] += dp(v[x][i], 1, x) + 1;
		else memo[x][c] += min(dp(v[x][i], 1, x) + 1, dp(v[x][i], 0, x));
	}
	
	return memo[x][c];
}

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

	cin >> n;
	for (int i = 0; i < n-1; i++) {
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}

	for (int i = 1; i <= n; i++) {
		if (v[i].size() == 1) {
			cout << dp(i, 0, -1) << endl;
			break;
		}
	}

	return 0;
}