백준 2533번 사회방 서비스(SNS) C++

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

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

 

 

트리에서 다이나믹 프로그래밍 문제이다.

진짜 너무 어렵다 이런거 어떻게 풀어야하는 걸까.

계속 하면 할 수 있겠지라 생각하며 계속 하는 수 밖에 없다.

 

* 트리에서 다이나믹 프로그래밍을 적용할 때는 보통

이번 노드에서의 dp값 다음 노드까지 포함했을 때 dp값으로 이어지는 top Down방식이거나 leaf까지 도달한 후 올라오며 값을 갱신하는 Bottom Up 방식을 사용하게 된다. 

 

이 문제는 Bottom Up 방식을 사용하게 된다. 두가지 선택지가 있는데 만약 루트부터 2개의 선택지를 고른다면 2^100만승으로 절대 풀어낼 수 없다. 그러므로 DP로 풀어낼 수 밖에 없다.

 

DP[노드넘버][0] = 이 노드를 얼리어답터가 아닌 일반인 일 때 최소 얼리어답터의 수

DP[노드넘버][1] = 이 노드를 얼리어답터라고 할 때 최소 얼리어답터의 수

 

알고리즘은 다음과 같다. 먼저 생각해야할 것은 목표 설정이다. 목표는 얼리어답터의 개수이다. 그러므로 우선 모든 사람들을 얼리어답터로 생각해보자. 그렇다면 첫 순회시 DP[노드넘버][1] = 1 로 설정하게 된다. 

이후 리프노드를 만난다면?

 

리프노드를 만나고 나서 부모로 한칸 올라온다. 이 때
DP[노드넘버][0] = DP[자식노드넘버][1] 가 되는데 이 노드가 일반인일 경우를 가정해보는 것이다. 만약 일반인이라면 반드시 이후 노드가 얼리어답터이어야하므로!

DP[노드넘버][1] = min(DP[자식노드넘버][0], DP[자식노드넘버][1]) 이 갱신은 내가 이미 얼리어답터이기 때문에 다음 노드는 일반인이 와도되고 얼리어답터가 와도된다. 때문에 둘 중 작은 수로 갱신한다.

 

언제나 그렇지만 정답을 알면 쉽다. 문제를 이해하고 푸는 방식을 이해해야 다음 부터는 온전히 내힘으로 풀 수 있다.

 

#include <iostream>
#include <vector>

using namespace std;

bool visited[1000001] = { false, };
int DP[1000001][2];						 // State는 두개이므로 얼리어답터 일 때와 아닐때
vector<int> node[1000001];

void dfs(int now) {
	DP[now][1] = 1;						// 1 = 얼리어답터, 0 = 일반인 얼리어답터는 무조건 1이상이므로 얼리어답터를 1로 설정

	for (int i = 0; i < node[now].size(); i++) {
		int nextNode = node[now][i];
		if (visited[nextNode]) continue;
		visited[nextNode] = true;
		dfs(nextNode);
		DP[now][0] += DP[nextNode][1]; // 일반인일 경우 반드시 얼리어답터가 들어와야하므로, 무조건 다음이 얼리어답터인 것만 가져옴
		DP[now][1] += min(DP[nextNode][1], DP[nextNode][0]); // 내가 얼리어답터이면 이전이 일반인인 경우와 얼리어답터인 경우 둘 중 하나를 선택할 수 있음.
	}
}

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

	int N;
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int pa, ch;
		cin >> pa >> ch;
		node[pa].push_back(ch);
        node[ch].push_back(pa);
	}

	visited[1] = true;
	dfs(1);

	cout << min(DP[1][1], DP[1][0]) << '\n';
}