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

출처: https://www.acmicpc.net/problem/2533

 Input 

8

1 2

1 3

1 4

2 5

2 6

4 7

4 8

 

 Output 

3

Greedy 방식

트리 구조이므로 "단말 노드 개수 ≥ 단말 노드 부모 개수"

이는 단말 노드를 얼리어댑터로 설정하는 것이

전체 얼리어댑터의 개수를 최소화하는데 도움이 되지 않습니다.

 

단말 노드보다 부모 노드를 얼리 어댑터로 설정하는 것이

전체 얼리어댑터 개수를 최소화하는 것입니다.

 

 

단말 노드를 얼리어댑터로 하지 않았다고 생각하면

단말 노드의 부모는 반드시 얼리어댑터이어야 합니다.

그리고 아랫부분을 제외해서 또 다른 부분 문제로 생각할 수 있습니다.

 

 

child가 모두 얼리어댑터라면 부모 노드는 얼리어댑터로 선택하지 않는다.

child에 얼리어댑터가 아닌 노드가 하나라도 있다면 얼리어댑터로 합니다.

Tree를 탐색할 때, BFS와 DFS 방식으로 부모-자식 관계를 알아낼 수 있습니다.

 

실제 얼리어댑터를 2, 3, 4로 해도 상관 없지만

정해둔 규칙을 적용하기 위해 1, 2, 4가 얼리어댑터로 설정됩니다.

 

 

※ BFS 탐색 코드

①을 통해 path[] = [0 0 1 1 1 2 2 4 4] 결과를 얻어냅니다.

    child들의 부모 노드들이 1, 2, 4 있음을 의미합니다.

② 중복해서 세면 안되므로 EA[] = [0 1 1 0 1 0 0 0]가 됩니다.

📌 DP 적용한 풀이

📌 BFS (Breadth-First Search, 너비 우선 탐색)

BFS (Breadth-First Search, 너비 우선 탐색)

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
const int LM = 1 << 20; 
struct Node {
    int child;
    Node* next;
    Node* alloc(int nc, Node* np) {
        child = nc, next = np;
        return this;
    }
}buf[LM * 2];
int bcnt;
int N, visit[LM], ans;
Node * adj[LM];
 
void input() {
    scanf("%d", &N);
    int i, u, v;
    for (i = 1; i < N; ++i) {
        scanf("%d %d", &u, &v);
        adj[u] = buf[bcnt++].alloc(v, adj[u]);
        adj[v] = buf[bcnt++].alloc(u, adj[v]);
    }
}
 
int DFS(int now) {
    visit[now] = 1;
    int ea = 0; // 얼리어댑터 여부
    for (Node *p = adj[now]; p; p = p->next) {
        int child = p->child;
        if (visit[child] == 0) {
            int rv = DFS(child);
            if (rv == 0) ea = 1;
        }
    }
    ans += ea;
    return ea;
}
 
int EA[LM], que[LM] = { 0 ,1 }, path[LM], fr = 1, re = 2;
void BFS() {
    visit[1] = 1;
    int now, child;
    for (; fr < re; fr++) {
        now = que[fr];
        for (Node *p = adj[now]; p; p = p->next) {
            child = p->child;
            if (visit[child] == 0) {
                visit[child] = 1;
                path[re] = fr;
                que[re++] = child;
            }
        }
    }
    for (re--; re; --re) {
        ans += EA[re];
        // re가 얼리어댑터가 아닌 경우
        EA[path[re]] |= !EA[re];
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    
    // DFS(1);
    BFS();
    printf("%d\n", ans);
}