[백준 15681][C++] 트리와 쿼리 (Gold 5)

[문제보기]

  15681. 트리와 쿼리

15681번: 트리와 쿼리

 

[풀이과정]

DFS 알고리즘을 이용하여 트리를 돌면서 서브트리의 노드 수를 저장해준다.

이때 말단 노드를 만나면 return 를 해주는 조건문을 넣어준다.(주의)

 

[소스코드]

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int MAX = 100001;
int N, Root, Q, ans;
vector<vector<int>> v;
bool visit[MAX];
int node_num[MAX] = {0};

int DFS(int node){
    if(node_num[node] != 0){
        return node_num[node];
    }

    visit[node] = false;

    int cnt = 1;
    for(int i=0; i<v[node].size(); i++){
        int next = v[node][i];
        if(visit[next] == false) continue;
        cnt += DFS(v[node][i]);
    }

    node_num[node] = cnt;
    return cnt;
}

int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);
    
    cin >> N >> Root >> Q;
    v = vector<vector<int>>(N+1, vector<int>());


    for(int i=0; i<N-1; i++){
        int a, b; cin >> a >> b;

        v[a].push_back(b);
        v[b].push_back(a);
    }

    memset(visit, true, sizeof(visit));
    node_num[Root] = DFS(Root);

    

    for(int i=0; i<Q; i++){
        int q; cin >> q;
        cout << node_num[q] << "\n";
    }
}

 

[해결과정 중 실수한 부분]