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

조민서·2022년 4월 26일

DFS 백준 지배 집합

PS

목록 보기

9/15

문제 : 사회망 서비스(SNS)

유형 : 트리의 지배 집합 찾기

문제 해석

친구 관계 그래프가 트리인 경우, 즉 모든 두 정점 사이에 이들을 잇는 경로가 존재하면서 사이클이 존재하지 않는 경우만 고려한다.
사회망 서비스에 속한 사람들은 얼리 어답터이거나 얼리 어답터가 아니다. 얼리 어답터가 아닌 사람들은 자신의 모든 친구들이 얼리 어답터일 때만 이 아이디어를 받아들인다.
지문에서 루트 없는 트리라는 사실을 알려주었다.

루트 없는 트리란?
사이클이 존재하지 않는 그래프는 노드 간의 상하 관계가 없을 뿐이지 트리와 같은 형태를 가지고 있는데, 이와 같은 그래프를 루트 없는 트리(unrooted tree)라고 부른다.

루트 없는 트리의 속성

정확히 V-1개의 간선이 있다.

사이클이 존재하지 않는다.

두 정점 사이를 연결하는 단순 경로가 정확히 하나있다.

이 조건들은 모두 동치로, 한 조건이라도 성립할 경우 다른 조건들이 모두 성립한다.

해결 전략

루트 없는 트리에서 트리의 최소 지배 집합을 찾는 가장 간단한 방법은 트리의 맨 아래에서부터 시작해서 위로 올라오면서 노드 선택 여부를 결정한다.

리프 노드는 자기 자신과 부모 노드밖에 지배하지 못하는 반면, 부모 노드는 그 외의 노드들도 지배할 수 있다. 따라서 리프 노드 대신 그 부모 노드를 선택해서 손해 볼 일은 절대로 없고, 리프 노드는 절대로 선택할 필요가 없다. 대신 그 부모 노드들은 모조리 선택한다. 이것을 정리하면 아래와 같다.

트리의 맨 밑에서부터 위로 올라간다.
- 리프 노드는 선택하지 않는다.
- 이 외의 노드에 대해, 트리의 맨 빝에서부터 올라오면서 다음과 같이 선택 여부를 결정한다.
  - 자기 자손 중 아직 지배당하지 않은 노드가 하나라도 있다면 현재 노드를 선택한다.
  - 이 외의 경우 현재 노드를 선택하지 않는다.

설계, 구현

양방향 연결을 통해 루트 없는 트리를 만든다.

방문 여부를 처리하기 위한 visited 배열을 0으로 초기화한다.

DFS를 진행한다.
1. 우선 처음에 리프 노드까지 들어간다.
  - 리프 노드는 무조건 선택하지 않으므로 얼리어답터가 아니다. 따라서 NOT_ADOPTER를 리턴한다.
2. 자식 노드를 통해 NOT_ADOPTER가 전달됐다면 현재 노드는 얼리어답터다. 따라서 EARLY_ADOPTER를 리턴하면서 얼리어답터 인원을 한 명 증가시킨다.
3. 자식 노드가 EARLY_ADOPTER라면 현재 노드는 얼리어답터가 아니다. 따라서 NOT_ADOPTER를 리턴한다.
4. 트리 맨 위에 도착하기 전까지 2, 3번 과정을 반복한다.

코드

#include <bits/stdc++.h>
#define MAX 1000001
using namespace std;

const int NOT_ADOPTER = 0;
const int EARLY_ADOPTER = 1;

int N;
vector<int> adj[MAX];
int visited[MAX];
int early_adopters;

void init() {
	cin >> N;
	int u, v;
	for(int i = 0; i < N - 1; i++) {
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

int dfs(int here) {
	visited[here] = true;

	int children[2] = {0, 0};
	for(int i = 0; i < adj[here].size(); i++) {
		int next = adj[here][i];
		if(!visited[next]) {
			children[dfs(next)]++;
		}
	}

	if(children[NOT_ADOPTER]) {
		early_adopters += 1;
		return EARLY_ADOPTER;
	}
	
	return NOT_ADOPTER;
}

void solve() {
	early_adopters = 0;
	dfs(1);
	cout << early_adopters;
}

int main() {
	init();
	solve();
	
	return 0;	
}