[백준] [C++] 2533번 사회망 서비스(SNS) (dfs, greedy)

1. 문제

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

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

유사한 문제: [그래프] GALLERY 감시 카메라 설치 (tistory.com)

[그래프] GALLERY 감시 카메라 설치

 

2. 풀이

이 문제는 탐욕법으로 문제를 해결할 수 있다.

 

주어진 트리를 dfs로 탐색하며,

 

탐색하면서 현재 상태에서 가장 최소가 되도록하는 노드가 얼리어답터라고 생각하는 것이다.

 

이에 대한 증명은 위의 감시카메라 설치 문제에서 나온

트리의 지배 집합찾기(dominating set)과 유사하다.

 

3. 트리 탐색

트리는 DAG(방향성이 있는 비순환 그래프)의 한 종류이다

 

주어진 입력에서 임의로 루트를 정하고, 부모노드를 임의의 배열에 기록하면 방향성을 결정할 수 있다.

 

dfs의 특징은 맨 끝 leaf 노드먼저 탐색한다는 것이다.

 

얼리어답터는 모두 연결된 노드가 얼리어답터이어야한다.

 

따라서 리프노드가 얼리어답터가 되려면 다음과 같은 상황이어야한다,

1) 부모노드가 얼리어답터

2) 자기자신이 얼리어답터

 

이 때 얼리 어답터의 개수를 최소화하는 것은 1번이다.

 

따라서 1번 부모노드가 얼리어답터가 될 수 있게

dfs 결과값으로 true를 리턴해주어 얼리어답터로 설정한다.

 

그리고 이렇게 설정된 얼리어답터의  부모는 모든 자식 노드가 얼리어답터가 될 수 있다.

따라서 이런 노드는 자기의 부모노드한테, 얼리어답터가되어달라고 하는것이 최소화하는 방향이므로, 

true를 리턴해주어야한다.

 

그 이후 리프노드들을 잘라 그 다음 부모노드가 리프노드라고 생각하며 반복하면

얼리어답터의 수의 최솟값을 얻어낼 수 있으며 dfs함수는 다음과 같다.

 

dfs(i) = i 번째 노드에서 연결된 모든 노드가 얼리어답터이면 true 리턴

 

#include <bits/stdc++.h>
 
using namespace std;
int N;
vector<vector<int> > adjList;
int answer = 0;
 
bool dfs(int idx, vector<bool>& visited) {
    int adjadaptor = 0;
    bool isadaptor = false;
    visited[idx] = true;
    for(int i = 0; i < adjList[idx].size(); i++) {
        int there = adjList[idx][i];
        if(visited[there]) continue;
        if(dfs(there, visited)) {
            isadaptor = true;
        }
        else {
            adjadaptor++;
        }
    }
    if(isadaptor) {
        answer++;
    }
    return (adjadaptor == adjList[idx].size() - 1);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>N;
    adjList = vector<vector<int> > (N);
    for(int i = 0; i < N-1; i++) {
        int a, b;
        cin>>a>>b;
        a--;b--;
        adjList[a].push_back(b);
        adjList[b].push_back(a);
    }
    vector<bool> visited(N, false);
    dfs(0, visited);
    cout<<answer<<"\n";
}