[백준] 15681 트리와 쿼리 DP + DFS

문제 : 

https://www.acmicpc.net/problem/15681

15681번: 트리와 쿼리

 

분석 :

밑에 알고리즘 분류를 보았을 때 '트리에서의 DP' 가 눈에 띄었다. 

트리에서의 DP ? 그게 뭐지 그러면 트리 자료 구조를 구현해야 하는 건가 ... 싶어 다른 블로그들을 참고하였다.

 

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

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

요 블로그를 보고 아하 트리를 직접 구현 하는게 아니라 트리를 탐색 할 수 있게끔 DFS로 접근하는 거구나 감이 잡혔고 DFS를 통해 트리 root를 타고 트리를 파고 드는데 그 값을 dp 배열에 저장한다는 점 ! 

생각보다 어렵진 않았지만 재귀를 사용해 풀었다는 점에서 추상적인것도 같았다. 

 

 

c++ 코드 :

//
//  15681_tree_query.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/09/08.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string.h>

using namespace std;
int n, root, query;
vector<int> node[100001];
int dp[100001];
int visit[100001];

int dfs(int now){
    
    if(visit[now] == true) { return dp[now]; }
    visit[now] = true;
    
    for(int i = 0; i < node[now].size(); i++){
        int next = node[now][i];
        if(visit[next] == true){ continue; }
        dp[now] = dp[now] + dfs(next); //자기 + 하위값
    }
    
    return dp[now];
    
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> root >> query;
    for(int i =0; i < n-1; i++){
        int start, end;
        cin >> start >> end;
        node[start].push_back(end);
        node[end].push_back(start);
    }

    memset(visit, false, sizeof(visit));
    
    for(int i =0; i <= n; i++){
        dp[i] = 1;
    }
    
    dfs(root);
    
    for(int i = 0; i < query; i++){
        int q;
        cin >> q;
        cout << dp[q] << '\n';
    }
    
    return 0;
}