백준11444 (사회망 서비스(SNS))[C/C++]

🔗링크

1. 문제 풀이

이 문제의 카테고리는 트리에서의 동적계획법이지만
나는 다른 방식으로 접근해보았다.

임의의 노드가 얼리 어답터가 아니다. -> 모든 인접 노드들은 얼리 어답터이다.

그렇다면 인접 노드가 많은 노드를 얼리 어답터로 선택하는 것이 가장 이상적이다.

트리에서 자식 노드가 가장 적은 노드는 리프 노드이기에 리프 노드는 얼리 어답터 후보에서 제외하게 되고 해당 리프 노드의 부모 노드는 반드시 얼리 어답터이여야 한다.

또한 얼리 어답터가 아닌 자식 노드를 가지는 노드는 반드시 얼리 어답터이여야 한다.

조금 주저리주저리 했지만 앞써 말한 것들로 조건을 세워본다면

1.리프 노드는 얼리 어답터가 될 수 없다.
2.모든 자식 노드가 얼리 어답터인 노드는 얼리 어답터가 아니여도 된다.
3.얼리 어답터가 아닌 자식노드를 가지는 노드는 얼리 어답터이다.

이 세가지 조건으로 코드를 구현하였다.

2. 코드

#include <stdio.h>
#include<vector>
using namespace std;

vector<int> Edge[1000001];
int V[1000001], res;

int f(int v) {
    V[v] = 1;
    int eax = 0, sub = 0;
    for (int i = 0; i < Edge[v].size(); i++) {
        if (!V[Edge[v][i]]) {
            eax += f(Edge[v][i]);
            sub++;
        }
    }
    if (eax && sub) {
    //얼리 어답터가 아닌 자식 노드 존재 and 리프 노드가 아니면 해당 노드는 얼리 어답터
        res++;
        return 0;
    }
    //그렇지 않으면 얼리 어답터X
    else return 1;
}

int main() {
    int N, u, v;
    scanf("%d", &N);
    for (int i = 0; i < N - 1; i++) {
        scanf("%d%d", &u, &v);
        Edge[u].push_back(v);
        Edge[v].push_back(u);
    }
    f(1);
    printf("%d", res);
    return 0;
}

3. 후기

dp를 통해 푸는것이 아닌 방법으로도 풀려서 나도 당황했다 사실,,