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

www.acmicpc.net/problem/2533

 

트리의 독립집합 foxtrotin.tistory.com/334 과 유사한 문제

 

얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 아이디어를 받아들인다

모든 사람이 새로운 아이디어를 수용하기 위해 필요한 최소 얼리 아답터의 수를 구하는 문제

 

친구 관계가 트리이기 때문에 트리에서의 다이나믹 프로그래밍을 할 수 있다

 

얼리 아답터는 주변 사람에게 영향을 준다. 즉, 얼리 아답터 둘이 붙어 있으면 비효율적이므로 떨어져 있어야 한다

이 말은 어떤 정점이 얼리 아답터라면 그 자식들은 전부 얼리 아답터가 아니라는 의미이기도 하다

하지만 어떤 정점이 얼리 아답터가 아니라면, 그 자식들은 얼리 아답터일 수도, 아닐 수도 있다(적어도 1명은 얼리 아답터여야 한다)

이런 점을 생각해 보면 트리의 독립집합 문제와 비슷한 접근이 가능하다. 식이 반대라는 점만 주의한다

 

D[v][0] : 정점 v가 얼리 아답터가 아닌 경우, 친구들의 수의 합

D[v][1] : 정점 v가 얼리 아답터인 경우, 각 자식들이 얼리 아답터이거나 아닌 때의 최솟값들의 합

 

D[v][0] 인 경우

정점 v가 얼리 아답터가 아닌 경우의 최솟값

정점 v가 얼리 아답터가 아니므로 자식은 얼리 어답터여야 한다

 

$w_i = v$의 자식일 때,

$D[v][0]=\sum D[w_i][1]$

 

D[v][1] 인 경우

정점 v가 얼리 어답터인 경우, 자식은 얼리 어답터일 수도, 아닐 수도 있다

 

$D[v][1]=\sum min(D[w_i][0], D[w_i][1])$

 

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int n, d[1000001][2];
bool chk[1000001];
vector<int> v[1000001];

void dfs(int now) {
	chk[now] = true; //방문했다고 체크한다
	d[now][0] = 0;
	d[now][1] = 1;
	for (int i = 0; i < v[now].size(); i++) { //모든 자식들에 대해
		if (chk[v[now][i]]) continue; //i를 방문한 적이 있다=부모를 의미하니까 패스
		dfs(v[now][i]);
		d[now][0] += d[v[now][i]][1]; //부모가 포함되지 않으면 자식은 포함이 되어야 함
		d[now][1] += min(d[v[now][i]][0], d[v[now][i]][1]); //부모가 포함되었으면 자식은 포함/안 포함 중에 작은 값
	}
}

int main() { 
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for (int i = 0, a, b; i < n - 1; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1);
	cout << min(d[1][0], d[1][1]);
	return 0;
}

 

같은 식으로 top-down방식으로도 풀 수 있다

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int n, d[1000001][2];
bool chk[1000001];
vector<int> v[1000001];

int dfs(int now, int isinclude) {
	int& res = d[now][isinclude]; //dp배열 값을 근본적으로 변경해 주어야 하기 때문에 참조형 변수이다
	//cout << res << endl;
	if (res != -1) return res; //이걸 안 해주면 여러 번 나올 수 있는 d[2][1]같은 값을 계속 계산해야 함
	chk[now] = true; //방문했다고 체크한다
	res = isinclude;

	for (int next = 0; next < v[now].size(); next++) { //모든 자식들에 대해
		if (chk[v[now][next]]) continue; //next를 방문한 적이 있다=부모를 의미하니까 패스
		if (isinclude == 0) res += dfs(v[now][next], 1); //부모가 포함되지 않으면 자식은 포함이 되어야 함
		else res += min(dfs(v[now][next], 0), dfs(v[now][next], 1)); //부모가 포함되었으면 자식은 포함/안 포함 중에 작은 값
	}
	chk[now] = false; //포함/안 포함 경우 때문에 최대 2번 다시 방문할 수도 있으니 체크를 풀어준다
	return res;
}

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

	cin >> n;
	for (int i = 0, a, b; i < n - 1; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	memset(d, -1, sizeof(d));
	cout << min(dfs(1, 0), dfs(1, 1));
	return 0;
}

 

다른 사람들 코드를 보니까 for문을 이렇게도 바꿀 수 있었다

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int n, d[1000001][2];
bool chk[1000001];
vector<int> v[1000001];

int dfs(int now, int isinclude) {
	int& res = d[now][isinclude]; //dp배열 값을 근본적으로 변경해 주어야 하기 때문에 참조형 변수이다
	//cout << res << endl;
	if (res != -1) return res; //이걸 안 해주면 여러 번 나올 수 있는 d[2][1]같은 값을 계속 계산해야 함
	chk[now] = true; //방문했다고 체크한다
	res = isinclude;

	for (int next : v[now]) {
		if (chk[next]) continue; //next를 방문한 적이 있다=부모를 의미하니까 패스
		if (isinclude == 0) res += dfs(next, 1); //부모가 포함되지 않으면 자식은 포함이 되어야 함
		else res += min(dfs(next, 0), dfs(next, 1)); //부모가 포함되었으면 자식은 포함/안 포함 중에 작은 값
	}
	chk[now] = false; //포함/안 포함 경우 때문에 최대 2번 다시 방문할 수도 있으니 체크를 풀어준다
	return res;
}

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

	cin >> n;
	for (int i = 0, a, b; i < n - 1; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	memset(d, -1, sizeof(d));
	cout << min(dfs(1, 0), dfs(1, 1));
	return 0;
}