[C++][BAEKJOON][TREE&DP] 2533번 사회망 서비스(SNS)

[문제]

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

[문제설명]
사회망 서비스(SNS)에 속한 사람들은 얼리 아답터이거나 얼리 아답터가 아니다. 얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 이 아이디어를 받아들인다. 어떤 아이디어를 사회망 서비스(SNS)에서 퍼뜨리고자 할 때, 가능한 한 최소의 수의 얼리 아답터를 확보하여 모든 사람이 이 아이디어를 받아들이게 하자.

 

얼리어답터의 조건은 다음과 같다.
- 얼리 어답터가 아니면, 모든 친구들이 얼리 어답터야 한다.
- 얼리 어답터이면, 주변 친구들이 얼리 어답터거나 아니어도 된다.

예를 들어, 8명의 사람으로 이루어진 위의 친구 관계 트리를 생각해보자. 2, 3, 4번 노드가 표현하는 사람들이 얼리 아답터라면, 얼리 아답터가 아닌 사람들은 자신의 모든 친구가 얼리 아답터이기 때문에 새로운 아이디어를 받아들인다.

주어진 친구 관계 그래프에서 아이디어를 전파하는데 필요한 얼리 아답터의 최소 수는 3이다.

 

[문제풀이]
DP를 이용한 브루트포스 알고리즘으로 풀어야한다.

leaf노드부터 or root노드부터 얼리어답터의 조건을 판별&갱신하면서 마지막 노드까지 전부 탐색해야, 얼리어답터의 최소 수를 구할 수 있기 때문이다. 나는 root 노드부터 DFS로 leaf 노드까지 탐색했다.

 

1) 우선 문제에서 주어진 트리는 각 노드당 연결된 노드들을 전부 동적으로 연결해주어야 하므로 벡터 배열을 사용했다.

vector<int> tree[MAX];

 

그리고 입력값을 양방향으로 연결해줬다.

tree[n].push_back(m);
tree[m].push_back(n);

 

2) DP는 leaf노드까지 탐색해야하므로 DFS를 사용했고, DP, visited 배열로 표현했다.

int dp[MAX][2];
bool visited[MAX];

 

3) 그리고 root 노드부터 DFS로 leaf노드를 찾는다. 이 때, 자신이 얼리어답터일 때와 얼리어답터가 아닐 때를 저장해준다. leaf노드에서 다시 돌아올 때, 이 값을 더해주면서 최소값을 찾을 거다.

dp[current_node][0] = 0; //내가 얼리어답터가 아니면 얼리어답터의 수를 늘려주지 않는다.
dp[current_node][1] = 1; //내가 얼리어답터라면 얼리어답터의 수를 하나 늘려준다.

 

4) 즉, 마지막 leaf노드에 도달했다면(연결된 자식노드가 더이상 없다면) DFS를 return하면서 현재 노드가 얼리어답터 일 때와 얼리어답터가 아닐 때를 최소값으로 갱신해준다.

dp[current_node][0] += dp[neighbor_node][1];//내가 얼리어답터가 아니면, 내 친구는 얼리어답터여야 한다 
dp[current_node][1] += min(dp[neighbor_node][0], dp[neighbor_node][1]);//내가 얼리어답터면, 친구는 얼리어답터여도 되고 아니어도 된다.

 

5) 마지막으로 root노드에 다달했다면 DFS 탐색 끝!
root노드가 얼리어답터 일 때와 얼리어답터가 아닐 때를 비교해서 최소값을 출력해준다.

min(dp[1][0], dp[1][1]);

 

[코드]

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

const int MAX = 1000001;

vector<int> tree[MAX];
int dp[MAX][2];
bool visited[MAX];

void SearchEarlyAdaptorNum(int);

int main() {
	int node_num = 0;
	cin >> node_num;

	int n = 0, m = 0;
	for (int i = 0; i < node_num; i++) {
		cin >> n >> m;
		tree[n].push_back(m);
		tree[m].push_back(n);//양방향으로 연결
	}
	SearchEarlyAdaptorNum(1);//root노드부터 DFS로 leaf노드까지 탐색
	cout << min(dp[1][0], dp[1][1]);//마지막 root노드의 값 출력

	return 0;
}

void SearchEarlyAdaptorNum(int current_node) {
	visited[current_node] = true;
	dp[current_node][0] = 0; //내가 얼리어답터가 아닐 때. 얼리어답터 1명 추가안함.
	dp[current_node][1] = 1; //내가 얼리어답터 일 때. 얼리어답터 1명 추가.
	for (int i = 0; i < tree[current_node].size(); i++) {
		int neighbor_node = tree[current_node][i];
		if (!visited[neighbor_node]) {
			SearchEarlyAdaptorNum(neighbor_node);//DFS
			//자식노드를 기반으로 역으로 채워주는 과정
			dp[current_node][0] += dp[neighbor_node][1];//내가 얼리어답터가 아니면, 내 친구는 얼리어답터여야 한다
			dp[current_node][1] += min(dp[neighbor_node][0], dp[neighbor_node][1]);//내가 얼리어답터면, 친구는 얼리어답터여도 되고 아니어도 된다.
		}
	}
}