쌓고 쌓다
[백준] 사회망 서비스(SNS) 2533번 C++ 풀이 본문
https://www.acmicpc.net/problem/2533
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> v[1000001];
int dp[1000001][2];
bool visit[1000001];
void solve(int x)
{
visit[x] = true;
dp[x][1] = 1;
for (int i = 0; i < v[x].size(); i++)
{
int child = v[x][i];
if (visit[child] == false)
{
solve(child);
dp[x][0] += dp[child][1];
dp[x][1] += min(dp[child][1], dp[child][0]);
}
}
}
int main(void)
{
cin.tie(0);
ios_base::sync_with_stdio(0);
memset(visit, false, sizeof(visit));
int N;
cin >> N;
for (int i = 0; i < N-1; i++)
{
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
solve(1);
cout << min(dp[1][0], dp[1][1]);
}
dp[정점A][0] : 정점A가 일반인일때 최소 얼리어답터의 수
dp[정점A][1] : 정점A가 얼리어답터일때 최소 얼리어답터의 수 입니다.
1번 노드에서 solve함수에 노드 1을 넣어 DFS 시작( solve(1) )을 합니다.
그러면 1번노드부터 연결된 노드를 방문하며 쭉쭉 내려가는데 아래의 순서로 코드를 작성합니다.
1단계 ) 방문 시 dp[방문한 노드][1] 를 1로 초기화해줍니다.
왜냐하면 자신이 얼리어답터일 경우의 최소 얼리어답터의 수를 나타내는 dp[방문한 노드][ " 1 " ] 에 자신이 얼리어 답터이므로 1로 바꿔주어야 합니다.
2단계 ) 방문한 노드의 자식 노드를 solve( 자식노드 ) 를 실행함으로써 자식 노드로 쭉쭉 타고 내려갑니다.
( 2 - 1단계 )
dp[ 노드 ] [ 0 ] 은 자신이 얼리어 답터가 아님을 나타내는데 이때 자식 노드는 반드시 얼리어 답터여야 합니다.
얼리어 답터가 아니라면 아이디어가 전파가 되지 않습니다. 그러므로 dp[노드][0]은 += 해주어야 하는데
dp[노드의자식][1] 을 더해주면 됩니다.
( 2 - 2단계 )
dp[ 노드 ] [ 1 ]은 자신이 얼리어 답터일때를 나타내는데 이때 자식은 얼리어답터이던지 아니던지 상관없이 아이디어를 전달 가능하므로 dp[ 노드 ] [ 1 ] 에 +=을 해줄 것인데 dp[노드의자식][0] 과 dp[노드의자식][1] 중 그냥 최솟값을 더해주면 됩니다. 왜 최솟값이냐면 모든 아이디어를 전달해야 하는데 최소한의 얼리어답터의 수로 해야 하기 때문입니다.
3단계 )
최종적으로 그냥 처음 solve(1)으로 노드1부터 시작했으므로 노드1의 dp[1노드][1]엔 노드1이 얼리어답터일 때의 최솟값과
dp[노드1][0]엔 노드1이 얼리어답터가 아닐 때 만족하는 최소 얼리어답터의 최솟값이 담겨 있으므로
둘 중 더 작을 값을 출력해주면 정답입니다.
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 연속합2 13398번 C++ 풀이 (0) | 2022.01.21 |
---|---|
[백준] 작업 2056번 C++ 풀이 (0) | 2022.01.20 |
[백준] 행복 15969번 C++ 풀이 (0) | 2022.01.17 |
[백준] 피시방 알바 1453번 C++ 풀이 (0) | 2022.01.08 |
[백준] 슈퍼 마리오 2851번 C++ 풀이 (0) | 2022.01.06 |