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

문제링크:www.acmicpc.net/problem/2533

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

어려웠습니다..ㅠㅠ

dp(up-down) 문제인건 인식했지만 우선 그래프를 어떤식으로 구현하고 dp를 구현할지 설계를 하는데 어려움을 겪었습니다.

 

• 1. 단방향 그래프 만들기
• 2. 그래프를 탐색하며 최소수 구하기

1. 우선 입력 받을때는 양방향으로 받고 재귀함수를 통해서 결과를 도출합니다.

void make_graph(int current, int parent) {
	if (parent != 0) {
		graph[parent].push_back(current);
	}
	
	for (int i = 0; i < vec[current].size(); i++) {
		if (parent == vec[current][i]) continue;
		make_graph(vec[current][i], current);
	}

}

parent 벡터에만 child 노드들을 넣어 놓음으로서 단방향 트리를 구현했습니다.

 

 

2. 그래프를 탐색하며 최소수 구하기는 일반적인 dp(up-down)과 흡사합니다. 

if (adapter) {
		ret = 1;
		for (int i = 0; i < graph[current].size(); i++)
			ret += min(solved(graph[current][i], adapter), solved(graph[current][i], !adapter));
	}
	else {
		ret = 0;
		for (int i = 0; i < graph[current].size(); i++)
			ret += solved(graph[current][i], !adapter);
	}

 1) 현재 노드가  얼리 어뎁터일때는 자식노드가  얼리 어뎁터일수도, 아닐수도 있습니다.

 2) 하지만 현재 노드가 얼리어뎁터가 아니라면  무조건 다음 노드는 얼리 어뎁터이어야 합니다.

2가지 조건을 통해서 재귀를 구현했습니다. 

 

 

 

아래는 정답코드입니다.

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


int n = 0;
vector <int> vec[1000001];
vector <int> graph[1000001];
int dp[1000001][2] = { 0, };

int solved(int current, bool adapter) {
	if (graph[current].empty()) {
		if (adapter)
			return 1;
		else
			return 0;
	}
	
	int &ret = dp[current][adapter];
	if (ret != -1)
		return ret;

	if (adapter) {
		ret = 1;
		for (int i = 0; i < graph[current].size(); i++)
			ret += min(solved(graph[current][i], adapter), solved(graph[current][i], !adapter));
	}
	else {
		ret = 0;
		for (int i = 0; i < graph[current].size(); i++)
			ret += solved(graph[current][i], !adapter);
	}

	return ret;

}

void make_graph(int current, int parent) {
	if (parent != 0) {
		graph[parent].push_back(current);
	}
	
	for (int i = 0; i < vec[current].size(); i++) {
		if (parent == vec[current][i]) continue;
		make_graph(vec[current][i], current);
	}

}

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

	cin >> n;
	for (int i = 0; i < n -1 ; i++) {
		int a, b;
		cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}

	make_graph(1, 0);
	/*
	for (int i = 0; i < n; i++) {
		cout << graph[i].size() << endl;
	}*/

	memset(dp, -1, sizeof(dp));
	cout << min(solved(1, 0), solved(1, 1)) << endl;
	return 0;
}