[C++] 2533번 사회망 서비스(SNS) - 트리, DP

#include <iostream>
#include <algorithm>
#include <vector>

#define FOR(i, k, N) for(int i=k; i<=N; i++)
#define MAX_N 1000001
#define INF 987654321

using namespace std;

int N;  //친구 관계 트리의 정점 개수 N
vector<int> tr[MAX_N];  //트리
int vi[MAX_N];  //visited?
int dp[MAX_N][2];  //(색칠되지 않았는가? // 색칠되었는가?)

void input()
{
    cin >> N;
    FOR(i, 1, N-1) {
        int u, v; cin >> u >> v;
        tr[u].push_back(v); tr[v].push_back(u);
    }
}

void DFS(int no)
{
    vi[no]=1;  //방문한 것 기록
    
    FOR(i, 1, tr[no].size()) {
        int next = tr[no][i-1];
        if(!vi[next]) {  //방문하지 않은 곳인 경우
            DFS(next);
            dp[no][0]+=dp[next][1];  //색칠 안되있으면 다음 노드가 색칠되어있어야 하고
            dp[no][1]+=min(dp[next][0], dp[next][1]);  //색칠되어있으면 상관 없음.
        }
    } dp[no][1]+=1;  //자신이 색칠되어있으면 +1
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    DFS(1);
    
    cout << min(dp[1][0], dp[1][1]);
    
    return 0;
}

사실 DP로 풀지 않고 0, 1, 0, 1로 풀어도 상관없었다는.... 그런 코드가 있었다는.... 그래서 아래에 적어놨다는...

 

굳이 DP로 풀지 않고 단순 DFS 탐색으로도 풀 수 있고 그러면 시간이 더 단축되어서 나온다.

 

 

 

 

 

 

 

<트리에서의 Dynamic Programming>

https://chanhuiseok.github.io/posts/algo-56/

알고리즘 - 트리 DP 문제 풀기(트리에서의 Dynamic Programming)

 

<참고한 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/7093213

로그인

 

 

 

 

 

 

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.