최소한의 얼리어댑터를 통해서 모든 사람에게 전파할 수 있는지 찾는 문제입니다.
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 |