개요

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

• 입력
  첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에지 (u, v)를 나타내는 두 정수 u와 v가 하나의 빈칸을 사이에 두고 주어진다.

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

접근 방식

1. 백준1949: 우수마을 문제와 유사하다.
   차이점은 우수마을 문제는 우수마을 아닌 마을끼리 인접할 수 있었지만,
   사회망서비스 문제는 어댑터가 아닌 친구끼리는 인접할 수 없다.

2. 기본적인 생각은 모든 사람이 어댑터일때와 아닐때를 조사를 해야하지만, 어댑터의 수가 최소가 될 때를 찾는 문제이므로 dp를 이용하여 푼다.

3. 각 서브트리의 루트가 어댑터일때/ 어댑터가 아닐때 재귀함수를 통해
   해당 서브트리의 어댑터 수의 최솟값을 return한다.

   루트노드의 각 자식은 루트노드의 상태와 반대값을 무조건 넣어줬는데,
   생각해보니 어댑터끼리는 인접해도 상관없으므로,
   루트노드가 어댑터라면 자식이 어댑터일때와 어댑터가 아닐때를 비교해
   더 작은값을 return하도록 구현하였다.

   //해당 노드가 어댑터인지 아닌지로 분기를 나눠 재귀를 하는 함수
   int SetLessEarlyAdapter(int node, bool isAdapter) {
   	//이미 구한값이면 바로 return
   	if (dp[node][isAdapter]) return dp[node][isAdapter];
   	//참조자 이용해 값을 바로 변경가능하게 함
   	int& ret = dp[node][isAdapter];
   	//자식 노드중에
   	for (int elem : tree[node]) {
      	   //기본적으로 루트의 상태와 반대값을 자식 노드에 넣어줌
   		int tmp = SetLessEarlyAdapter(elem, !isAdapter);
   		//어댑터끼리는 둘이 인접해도 되므로 비교해서 더 작은값을 저장
   		if (isAdapter) tmp = min(tmp, SetLessEarlyAdapter(elem, isAdapter));
   		//자식값들의최소값 다 더해야 한다.
   		ret += tmp;
   	}
   	//자신이 어댑터라면 1 더해줌
   	if (isAdapter) ret += 1;
   	return ret;
   }

전체코드

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

vector<vector<int>> adj,tree;
vector<bool> visited;
int Nodes;
int dp[1'000'001][2];

void MakeTree(int Node) {
	visited[Node] = true;
	for (int elem : adj[Node]) {
		if (visited[elem]) continue;
		tree[Node].push_back(elem);
		MakeTree(elem);
	}
}

//해당 노드가 어댑터인지 아닌지로 분기를 나눠 재귀를 하는 함수
int SetLessEarlyAdapter(int node, bool isAdapter) {
	//이미 구한값이면 바로 return
	if (dp[node][isAdapter]) return dp[node][isAdapter];
	//참조자 이용해 값을 바로 변경가능하게 함
	int& ret = dp[node][isAdapter];
	//자식 노드중에
	for (int elem : tree[node]) {
		int tmp = SetLessEarlyAdapter(elem, !isAdapter);
		//어댑터아닌사람이 둘이 있을 순없음
		if (isAdapter) tmp = min(tmp, SetLessEarlyAdapter(elem, isAdapter));
		//자식값들의최소값 다 더해줌
		ret += tmp;
	}
	//자신이 어댑터라면 1 더해줌
	if (isAdapter) ret += 1;
	return ret;
}

void Input() {
	int tmpNode1=0, tmpNode2=0;
	cin >> Nodes;
	adj.resize(Nodes + 1);
	tree.resize(Nodes + 1);
	visited.resize(Nodes + 1);
	for (int i = 0; i < Nodes-1; i++) {
		cin >> tmpNode1 >> tmpNode2;
		adj[tmpNode1].push_back(tmpNode2);
		adj[tmpNode2].push_back(tmpNode1);
	}
	MakeTree(tmpNode1);
	cout << min(SetLessEarlyAdapter(tmpNode1, false), SetLessEarlyAdapter(tmpNode1, true));
}

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

문풀후생

바로 인접한 친구끼리는 상태가 무조건 반대여야하는 줄 알고,
SetLessEarlyAdapter함수 내부의

	//자식 노드중에
	for (int elem : tree[node]) {
		int tmp = SetLessEarlyAdapter(elem, !isAdapter);
		//어댑터아닌사람이 둘이 있을 순없음
		if (isAdapter) tmp = min(tmp, SetLessEarlyAdapter(elem, isAdapter));
		//자식값들의최소값 다 더해줌
		ret += tmp;
	}

이 부분을

	//자식 노드중에
	for (int elem : tree[node]) {
		int tmp = SetLessEarlyAdapter(elem, !isAdapter);
		//자식값들의최소값 다 더해줌
		ret += tmp;
	}

이렇게 짰었다.
당연히 예제부터 틀렸고 생각해보니
어댑터인 친구가 인접했을 때, 더 어댑터 갯수가 작아지는 반례가 존재했다.