[BOJ] 2533 : 사회망 서비스(SNS)

문제 링크

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

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

트리로 이루어진 사회관계망에서 모두가 새로운 것을 받아들이기 위해 필요한 최소 얼리어답터 수를 구하는 문제.

풀이

기존의 DP문제와는 다르게 트리와 DP가 합쳐진 문제.

하나의 정점에 대해서 우리는 2가지 경우로 나눠서 볼 수 있다. 해당 정점이 얼리어답터이거나 얼리어답터가 아니거나.

0을 얼리어답터인 경우, 1을 얼리어답터가 아닌경우로 생각하고 DP배열을 2차원으로 나눴다.

DP[i][0] 과 DP[i][1].

DP[i][0]에는 정점 i가 얼리어답터인 경우에 필요한 얼리어답터의 최소 수를 저장하고

DP[i][1]에는 반대로 정점 i가 얼리어답터가 아닌 경우에 필요한 얼리어답터의 최소 수를 저장한다.

정점 i의 임의의 자식노드를 child 라고 한다면, i가 얼리어답터인 경우에는 child가 얼리어답터이든 아니든 상관없다.

DP[i][0] += min(DP[child][0], DP[child][1])

i가 얼리어답터가 아닌 경우에는 child가 모두 얼리어답터여야만 한다.

DP[i][1] += DP[child][0]

이 점화식을 정점 i의 모든 자식노드에 대해 실행해주면 된다.

여기서 점화식은 Bottom-up 방식으로 채워져야한다. 최하위 노드(?) 즉, 리프노드부터 값을 채워나가야 한다. 그렇기 때문에 재귀를 이용해서 가장 깊은곳까지 내려가서 DP배열을 채워나간다.

한 번 방문한 노드는 재방문할 필요가 없으므로 visited 배열을 이용해서 중복을 방지했다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 1000000 + 5;
int N;
vector<int> Child[MAX_N];
int DP[MAX_N][2]; //0은 얼리어답터 일때, 1은 아닐때
bool visited[MAX_N];
 
void travel(int now) {
    visited[now] = true;
    DP[now][0] = 1;
    for (int i = 0; i < Child[now].size(); i++) {
        int child = Child[now][i];
        if (visited[child])
            continue;
        travel(child);
        DP[now][0] += min(DP[child][0], DP[child][1]);
        DP[now][1] += DP[child][0];
    }
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        int P, C;
        cin >> P >> C;
        Child[P].push_back(C);
        Child[C].push_back(P);
    }
    travel(1);
    cout << min(DP[1][1], DP[1][0]) << "\n";
    return 0;
}
 

왜 시작점을 1로 지정했느냐. 사실 이 문제에서 루트를 지정해주지 않았기 때문에 루트노드를 어떤 정점으로 봐도 상관없다. 그래서 나는 편의상 1을 넣어준 것이다. 하지만 1을 넣었다는 것은 루트노드를 1로 보겠다는 것이기 때문에 마지막에 DP[1][1]과 DP[1][0]을 비교해서 작은 값을 출력해준다. 1~N 사이에 있는 아무 노드를 루트노드로 봐도 상관은 없다.

=> 그리고 루트가 정해져있지 않기때문에 엣지를 양방향으로 설정해야한다.