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

 

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

 

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

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

---

 

해결전략

 

다이나믹 프로그래밍 Dynamic Programming
트리 Tree
깊이우선탐색 DFS

---

 

정답 코드

 

#include <iostream>
#include <algorithm> // min 함수 알고리즘 
#include <vector> 
#include <cstring>  // memset 함수를 위한 라이브러리
using namespace std;

int n; 						// 노드의 개수
vector<int> graph[1000001]; // 그래프 정보를 저장하는 벡터 배열
int dp[1000001][2]; 		// 다이나믹 프로그래밍을 위한 배열, 선택 여부에 따른 최소 노드 개수를 저장

int DFS(int curr, int prev, int state) // curr: 현재 노드, prev: 이전 노드, state: 선택 여부
{
	if (dp[curr][state] != -1) return dp[curr][state]; // 이미 계산된 값이면 재활용

	int answer = 0;

	if (state == 0) // 현재 노드를 선택하지 않는 경우
	{
		for (int i = 0; i < graph[curr].size(); i++) // 모든 자식 노드에 대해
		{
			int next = graph[curr][i];

			if (next == prev) continue; // 부모 노드면 패스

			answer += DFS(next, curr, 1); // 자식 노드를 선택
		}

		return dp[curr][state] = answer; // 계산 결과 저장 후 반환
	}
	else // state == 1 인 경우, 현재 노드를 선택하는 경우
	{
		for (int i = 0; i < graph[curr].size(); i++) // 모든 자식 노드에 대해
		{
			int next = graph[curr][i];

			if (next == prev) continue; // 부모 노드면 패스

			answer += min(DFS(next, curr, 0), DFS(next, curr, 1)); // 자식 노드를 선택하거나 선택하지 않는 경우 중 최소값
		}

		return dp[curr][state] = answer + 1; // 현재 노드를 선택했으므로 +1 후 계산 결과 저장 후 반환
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	memset(dp, -1, sizeof(dp)); // dp 배열 초기화

	for (int i = 0; i < n-1; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	cout << min(DFS(1, 0, 0), DFS(1, 0, 1)); // 루트 노드부터 시작하여 선택하거나 선택하지 않는 경우 중 최소값 출력

	return 0;
}

 

 

• 현재 노드가 얼리어답터 X 인 경우
  • 인접한 노드가 무조건 얼리어답터 O 여야 한다.
  • dp( curr, prev, 0 );
• 현재 노드가 얼리어답터 O 인 경우
  • 인접한 노드가 얼리어답터 X와 O 모두 가능
  • dp( curr, prev, 1 ) = min( dp(next, curr, 0), dp(next, curr, 1) );

 

 

---