백준 - 15681 트리와 쿼리

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

15681번: 트리와 쿼리

트리 + 동적계획법 문제이다.

 

트리 자체가 재귀적 속성이 있으므로 dfs를 사용하면 트리를 만들 수 있다.

 

 

 

 

트리 구현 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Node {
    int data;
    // int numChildren = 0;
    vector<Node*> children;
};

vector<int> numChildren;

vector<vector<int>> adj;
vector<bool> visited;

Node* root;

int N, R, Q;

Node* dfs(int cur) {
    Node* ret = new Node();
    ret->data = cur;
    visited[cur] = true;

    for(int i = 0; i < adj[cur].size(); i++) {
        int next = adj[cur][i];
        if(visited[next]) continue;
        ret->children.push_back(dfs(adj[cur][i]));
    }

    for(int i = 0; i < ret->children.size(); i++) {
        numChildren[cur] += numChildren[ret->children[i]->data] + 1;
    }

    return ret;
}

int main() {
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> R >> Q;
    adj.assign(N + 1, vector<int>());
    numChildren.assign(N + 1, 0);
    visited.assign(N + 1, false);

    int u, v;
    for(int i = 0; i < N - 1; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int target;
    root = dfs(R);

    for(int i = 0; i < Q; i++) {
        cin >> target;
        cout << numChildren[target] + 1 << '\n';
    }


    return 0;
}

 

 

단순 dfs 활용

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> adj;
vector<int> cache;
vector<bool> visited;

int N, R, Q;

int dfs(int node) {
    visited[node] = true;

    int& ret = cache[node];
    
    for(int i = 0; i < adj[node].size(); i++) {
        int next = adj[node][i];
        if(visited[next]) continue;
        ret += dfs(next);
    }

    return ++ret;
}

int main() {
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> R >> Q;

    adj.assign(N + 1, vector<int>());
    cache.assign(N + 1, 0);
    visited.assign(N + 1, false);

    
    int u, v;
    for(int i = 0; i < N - 1; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(R);

    
    int target;
    for(int i = 0; i < Q; i++) {
        cin >> target;
        cout << cache[target] << '\n';
    }

    return 0;
}

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~