[G3] 백준 2533번 사회망 서비스(SNS) C++ 트리에서의 다이나믹 프로그래밍

리뷰

 

트리에서의 다이나믹 프로그래밍을 활용하여 얼리어답터의 최소 갯수를 구하는 문제

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

 

전역 변수

• n : 노드의 개수
• lst : 인접 리스트를 통해 노드간 양방향 간선 정보를 저장할 2차원 정수형 벡터
• dp : 각 노드가 얼리어답터일때와 아닐때의 정보를 저장할 배열
• v : dfs탐색 시 노드의 방문 정보를 저장할 배열

 

함수

1. dfs

void dfs(int cn)

 

1. 깊이 우선 탐색을 통해 얼리어답터의 개수를 재귀적으로 구해줄 함수
2. 현재 노드를 매개변수를 통해 전달받고, 각 인접리스트의 노드를 매개변수로 전달해 준다.
3. 함수 실행 시 현재 노드가 얼리어답터일때는 1, 아닐때는 0으로 초기값을 세팅해 준다.
4. 인접리스트를 순회하고 자식 노드가 방문하지 않았을 경우 우선적으로 재귀를 수행한다.
5. 재귀를 빠져나온 후 현재 노드의 얼리어답터가 아닐 경우 자식 노드가 얼리어답터일 경우의 값을 더해준다.
6. 현재 노드가 얼리어답터일 경우 자식 노드가 얼리어답터가 아닐 경우와 맞을 경우 중 최소값을 더해준다.
7. 모든 재귀가 종료된다면 루트 노드에 얼리어답터일 경우와 아닐 경우의 값이 모두 저장된다.

 

문제풀이

1. n값을 입력 받고, 인접리스트를 저장할 벡터를 n + 1크기로 저장해 준다.
2. n - 1개의 간선 정보를 입력 받아 양방향 간선으로 추가해 준다.
3. 루트 노드에 방문처리를 해준 후 루트로부터 깊이 우선 탐색을 진행해 준다.
4. 1번 노드가 얼리어답터인 경우와 아닐 경우의 최소값을 구해 출력해 준다.

 

참고 사항

1-based-indexing이므로 인접 리스트를 n + 1크기로 설정해 주었다.

dp정보는 dfs함수가 실행되었을때 자기자신을 한번 초기화 해주고, 자식노드의 재귀가 마친 후에 추가 작접을 해준다.

 

 

정답 코드

#include<iostream>
#include<vector>

using namespace std;
int n;
vector<vector<int>> lst;
int dp[1000001][2];
int v[1000001];

void dfs(int cn) {
	dp[cn][0] = 0;
	dp[cn][1] = 1;
	for (int nn : lst[cn]) {
		if (v[nn]) continue;
		v[nn] = 1;
		dfs(nn);
		dp[cn][0] += dp[nn][1];
		dp[cn][1] += min(dp[nn][0], dp[nn][1]);
	}
}

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

	cin >> n;
	lst.resize(n + 1);
	for (int i = 0; i < n - 1; i++) {
		int n1, n2; cin >> n1 >> n2;
		lst[n1].push_back(n2);
		lst[n2].push_back(n1);
	}
	v[1] = 1;
	dfs(1);
	cout << min(dp[1][0], dp[1][1]);
}