[백준] 사회망 서비스(SNS) 2533번 (c++) 그래프에서 dp

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

 

풀이 방법

우선 완전 탐색을 이용해서 풀이했었다. 하지만 시간 초과가 발생한다.

 

해당 문제를 dp로 풀이하기 위해선 문제를 나누는 것이 가장 중요하고(순서를 정하기 위해), 이를 위해서 트리를 만들어야 한다.

루트노드는 임의로 설정해도 상관이 없다. (첫 번째 노드로 설정)

 

트리를 만들었으므로 자식과의 관계만 고려하면 된다.현재가 얼리 아답터면 자식은 얼리 아답터, 얼리 아답터가 아닌경우 상관이 없으므로 둘 중 최솟값을 현재 노드의 dp에 더해준다.

만약 현재가 얼리 아답터가 아니면 자식은 무조건 얼리 아답터가 되어야 하기 때문에 해당 경우만 더해준다.

모든 자식을 돌며 자식의 dfs 값을 더해주면 된다.

그리고 마지막 리프 노드를 처리하기 위해, 자신이 얼리 아답터이면 dp의 값을 1로, 얼리 아답터가 아니면 dp의 값을 0으로 설정하고 for 문을 통해 자식 노드를 탐색한다.

 

코드

#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;
int n;
int visited[1000001];
vector<int> V[1000001];
vector<int> Tree[1000001];
int dp[1000001][2];

void Input(){
    cin >> n;
    for (int i = 0; i < n - 1; i++){
        int a, b; 
        cin >> a >> b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    

}

void make_tree(int node) { //트리를 만든다.
    visited[node] = 1;

    for (int i = 0; i < V[node].size();i++) {
        if (visited[V[node][i]] == 0) {
            Tree[node].push_back(V[node][i]);
            make_tree(V[node][i]);
        }
    }
}

int dfs(int cur, int state) { // 현재랑 현재 state 1이면 현재가 얼리 아답터 0이면 현재가 얼리 아답터가 아니다.
    if (dp[cur][state] != 0) return dp[cur][state];
    if (state == 1) { // 현재를 얼리 아답터로 한다. (자식은 얼리 아답터, 얼리 아답터 아니든 상관이 없다.)
        dp[cur][state] = 1;
        for (int i = 0;i < Tree[cur].size();i++) { //자식을 순회하며 해당 자식의 경우를 탐색한다.
            dp[cur][state] += min(dfs(Tree[cur][i], 0), dfs(Tree[cur][i], 1)); 
        }
    }
    else { // 현재가 얼리 아답터가 아니기 때문에 자식은 무조건 얼리 아답터가 되야 한다.
        dp[cur][state] = 0; 
        for (int i = 0;i < Tree[cur].size();i++) {
            dp[cur][state] += dfs(Tree[cur][i], 1);
        } 
    }

    return dp[cur][state];
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);    
    memset(visited, 0, sizeof(visited));
    
    Input();
    make_tree(1);
    int ans = min(dfs(1, 0), dfs(1, 1));
    cout << ans << '\n';
    return 0;

}