끄적끄적 코딩
article thumbnail

최소한의 얼리어댑터를 통해서 모든 사람에게 전파할 수 있는지 찾는 문제입니다.
DP와 DFS방식을 사용하여 문제를 해결하였습니다.

case1 : 현재 탐색중인 노드가 얼리어댑터인 경우
     => 이웃한 노드는 얼리어댑터일수도 아닐수도 있습니다.

case2 : 현재 탐색중인 노드가 얼리어댑터가 아닌 경우
      => 이웃한 노드는 얼리어댑터이어야 합니다.

check[1000001][2]
1000001 => 100만명의 사람에 대한
2 => 0 : 얼리어댑터가 아님, 1 : 얼리어댑터가 맞음

이를 식으로 바꾸면 다음과 같습니다.

check[now][0] += check[next][1];  //case1
check[now][1] += min(check[next][0], check[next][1]); //case2

 

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

bool visit[1000001];
int check[1000001][2];
vector<vector<int> > v;

void dfs(int now)
{
	int next;
	
	visit[now] = true;
	check[now][1] = 1;
	
	for(int i=0; i<v[now].size(); ++i) {
		next = v[now][i];	
		if(visit[next]) {
			continue;
		}
		dfs(next);
		check[now][0] += check[next][1];
		check[now][1] += min(check[next][0], check[next][1]);
	}
}

int main(int argc, char *argv[])
{
	int n;
	int a, b;
	
	cin >> n;
	
	v.resize(n + 1);
	
	for(int i=1; i<n; ++i){
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	dfs(1);
	
	cout << min(check[1][0], check[1][1]) << endl;;
		
	return 0;
}

'알고리즘' 카테고리의 다른 글

[C++] 백준 11657번 타임머신  (0) 2021.08.25
[C++] 백준 2252번 줄 세우기  (0) 2021.08.25
[C++] 백준 14226번 이모티콘  (0) 2021.08.24
[C++] 백준 1926번 그림  (0) 2021.08.18
[C++] 백준 1715번 카드 정렬하기  (0) 2021.08.09

검색 태그