백준, boj) 2533. 사회망 서비스(SNS)( C / C++)

1. 문제 링크

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

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

2. 문제 개요

 친구 관계 그래프를 이용해서 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정을 이해하는데 도움을 줄 수 있다. 어떤 새로운 아이디어를 먼저 받아들인 사람을 얼리어답터(early adaptor)라고 하는데, 사회망 서비스에 속한 사람들은 얼리 어답터이거나 얼리 어답터가 아니다.

 

친구 관계 트리가 주어졌을 때, 모든 개인이 새로운 아이디어를 수용하기 위하여 필요한 최소 얼리어답터의 수를 구하는 프로그램을 작성하자.

 

3. 문제 힌트

Tree형태의 DP.

탐색을 위해 DFS로 Tree를 다시 만들어야 한다. ( 꼭 안 만들어도 됨.)

 

Action.

내가 얼리어답터라면, 나의 친구들은 얼리어답터여도 되고 아니어도 된다.

내가 얼리어답터가 아니라면 나의친구들은 얼리어답터여만 한다.

 

4. 문제 풀기

문제를 잘 읽어보면 Minimun Vertex Cover문제다. 가장 적은 정점(사람)으로 모든 사람들을 덮어야 하기 때문이다.

(최소 버텍스는 edge를 덮는것이긴 한데.. Tree형태니까 상관없을 것 같다. )

 

그래서 이분매칭으로 하자니 N의 범위가 너무 크다.

DP를 사용하자.

 

처음 제출한 답안은 문제를 양방향 간선으로 받고 DFS를 사용하여 경로를 결정지어주는 트리를 따로 만들어서 진행했다. 그러니 실행시간이 1300ms정도 나왔는데, 다른 사람들 제출한 것을 보니 1000ms도 꽤나 있어서 최적화를 해줄 수 있는 점이 없을까 찾아보다가 DFS트리를 꼭 안 만들어줘도 될 것 같아서 만들어주지 않고 진행했다.

 

동적 계획법의 관점에서 봤을 때, (state = {0, 1} n = {1... N}이다)

dp(n,0)는 n번 정점이 얼리어답터가 아닐 때의 최소 얼리어답터의 수.

dp(n,1)는 n번 정점이 얼리어답터일 때의 최소 얼리어답터 수라고 하자.

 

보통 Root를 잡아야 하지 않는가?라고 의문을 가질 수 도 있다.

하지만 이 주어진 그래프는 Tree이고 어느 점을 잡고 Tree를 들면 Rooted Tree가 된다. 따라서 1~N번 정점 중 아무거나 잡고 DP를 실행해도 된다.(어느 점을 잡아도 Root가 되고, 똑같은 값을 반환한다는 의미)

 

일단 인접 그래프는 리스트의 형태로 해주자. 행렬로 하면 1M x 1M이 되어야 한다..

양방향으로 입력받아준다.

여기서 DFS로 단방향으로 모든 정점을 탐색하는 Tree를 얻을 수 있지만 만들지 않고 진행하겠습니다.

 

min(dp(1, 0, 0), dp(1, 0, 1))

dp(현재 노드, 이전 노드, 선택 여부)라고 보면 된다.

이 문제에서 구해야 하는 것은 위와 같다. DFS를 사용해서 Tree를 만들어 준다면 두 번째 인덱스는 필요 없을 것이다. 결국 1번 노드가(아무거나 괜찮음) 얼리어답터가 아닌 경우의 최솟값, 얼리어답터인 경우의 최솟값 두 개를 비교하는 것이다.

 

dp함수를 만들어보면,

기저 조건이 되는 부분은 작성할 필요가 없다. 인덱스를 벗어나거나 그런 경우가 없기 때문에..

메모이제이션 부분이 가장 먼저 오게 된다.

 

그 후,

얼리어답터로 할 것인지, 하지 않을 것인지로 크게 2개의 분류로 나뉘게 된다.

 

만약에 

트리 예제

위의 그림과 같이 트리가 있다면, 1번 정점 기준으로 생각해보자. 구름도 트리이다.

dp(2)의 최솟값이 x dp(3)은 y dp(4)는 z이다.

1의 자식인 2, 3, 4의 밑에 있는 트리들에서 가장 적게 필요한 얼리어답터의 수이다.

 

그럼 1이 얼리어답터라면 x+y+z + 1(노드 1번도 추가하므로 1)이 될 것이고, 노드 1번이 얼리어답터가 아니라면 x+y+z에서 끝날 것이다. 이처럼 자식들의 최솟값들을 다 더해주어야 한다.

자식들을 탐색할때 DFS트리를 만들어 주지 않았기 때문에 이전 정점이 아니라는 것을 구분하는 if문이 들어가야한다.

 

(3) 번 문제 힌트에 있듯이,

내가 얼리어답터가 아니라면 인접한 노드는 얼리어답터여만 한다.

dp(cur, pre,0) = dp(next, cur,1)

 

내가 얼리어답터라면 인접한 노드는 얼리어답터여도 되고 아니어도 된다.

dp(cur, pre,1) = min(dp(next, cur,0) , dp(next, cur,1))

 

이것이 재귀적으로 이루어진다고 보면 된다.

 

 

5. 코드

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

vector<vector<int>> adj;
int dp_table[1000001][2];
int n;

int dp(int cur, int pre, int state)
{
	int &cache = dp_table[cur][state];
	if (cache != -1)return cache;
	int ans = 0;
	if (state == 0) {
		int len = adj[cur].size();

		for (int i = 0; i < len; ++i) {
			int next = adj[cur][i];
			if (next == pre)continue;
			ans += dp(next, cur, 1);
		}
		return cache = ans;
	}
	else
	{
		int len = adj[cur].size();
		int ret1 = 0, ret2 = 0;
		for (int i = 0; i < len; ++i) {
			int next = adj[cur][i];
			if (next == pre)continue;
			ret1 = dp(next, cur, 0);
			ret2 = dp(next, cur, 1);
			ans += min(ret1, ret2);
		}
		return cache = ans + 1;
	}
}


int main()
{
	scanf("%d", &n);
	adj.resize(n + 1);
	memset(dp_table, -1, sizeof(dp_table));

	for (int i = 0; i < n - 1; ++i) {
		int from, to;
		scanf("%d %d", &from, &to);
		adj[from].push_back(to);
		adj[to].push_back(from);
	}

	printf("%d", min(dp(1, 0, 0), dp(1, 0, 1)));
	return 0;
}

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~