[백준] 2533 사회망 서비스(SNS)

문제 주소 : www.acmicpc.net/problem/2533

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

fast io 미적용

문제 확인

 

트리에서 dp 문제입니다. 

얼리 어답터인 경우 친구는 얼리 어답터이거나 아닐 수 있지만 자신이 얼리 어답터가 아닌 경우 친구 중 한 명은 꼭 얼리 어답터이어야 함을 이용합니다. 이 말은 즉 자신의 모든 친구가 얼리 어답터가 아니라면 자신이 얼리 어답터가 돼야 함을 의미하고 반대로 모든 친구가 얼리 어답터라면 나 자신은 어답터일 필요가 없습니다.

 

풀이

 

depth 조절과 효율성을 위해 그래프 작성을 조금 다르게 합니다.

그래프 간선을 저장하며 간선 정보에는 목적지, 다음 간선의 번호로 나타냅니다.

undirect 그래프 이므로 입력받은 u, v 값을 (u, v), (v, u) 모두 저장하며 간선의 번호를 매기고 이를 저장해둡니다.

dfs 탐색 시 해당 간선이 시작하는 인덱스를 s_idx로 불러오고 간선들을 탐색합니다.

 

탐색시 depth가 가장 깊은 리프 노드를 얼리 어답터로 두는 것보다 리프 노드의 부모 노드를 얼리 어답터로 두는 것이 더 적은 수를 사용할 수 있습니다. 그 후 상위 노드의 경우 주변에 어답터가 없다면 자신을 어답터로 만들어 채워 나갑니다.

 

코드

#include <iostream>
using namespace std;
typedef struct node {
    int dest;
    int link;
};
node vtx[2000000 - 1];
int s_idx[1000001], res;
bool dfs(int cur, int prev) {
    bool is_adaptor = false;
    for (int i = s_idx[cur]; i;) {
        int dest = vtx[i].dest;
        if (dest != prev) {
            if (!dfs(dest, cur))
                is_adaptor = true;
        }
        i = vtx[i].link;
    }
    if (is_adaptor)
        res++;
    return is_adaptor;
}
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
    for (int i = 0, cur = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        vtx[++cur] = { v, s_idx[u] };
        s_idx[u] = cur;
 
        vtx[++cur] = { u, s_idx[v] };
        s_idx[v] = cur;
    }
    dfs(1, 0);
    printf("%d", res);
}