문제 푼 날짜 : 2021-10-01

문제

문제 링크 : https://www.acmicpc.net/problem/15681

접근 및 풀이

Tree에서 DP를 이용하여 푸는 문제였다.
우선 문제의 모든 입력을 받아준 후, Root부터 시작하여 dfs로 탐색해준다.
이 때 탐색하면서 중요한건 메모이제이션을 활용하는 것이다. 이를 위해 dp 배열을 선언하였고, 이 배열이 의미하는 것은 각 노드를 정점으로 하는 서브트리에 속한 정점의 갯수이다.
이를 이용하여 Tree를 따라 탐색하면서 dp 배열을 업데이트시켜주었다.

코드

// 백준 15681번 : 트리와 쿼리
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

vector<int> tree[100001];
int dp[100001];

int dfs(int now) {
    int &ret = dp[now];
    if (ret != -1) {
        return ret;
    }
    
    ret = 1;
    for (int i = 0; i < tree[now].size(); i++) {
        int next = tree[now][i];
        if (dp[next] != -1) { // 부모노드 재방문 가지치기
            continue;
        }
        ret += dfs(next);
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N, R, Q;
    cin >> N >> R >> Q;
    
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    dfs(R);
    
    while (Q--) {
        int node;
        cin >> node;
        cout << dp[node] << '\n';
    }
    return 0;
}

결과

피드백

Tree에서 DP를 적용하여 푸는 문제 대부분은 개인적으로 아주 어려운 난이도의 문제들이라고 생각한다. 이 문제는 이런 종류의 문제 중 아주 기초적인 문제인 것 같다.