[백준/C++] 트리와 쿼리 (No. 15681)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 루트노드가 주어지면 그 노드를 기준으로 트리를 그리면 되는 문제다.

 

단지 그냥 트리를 그리는 것과 다른 점이 있다면, 자식 노드의 수가 몇 개 인지 쿼리를 통해 출력한다는 점이다.

 

여기서 매번 쿼리가 들어올 때 마다 자식 노드의 수를 계산한다면 매우 많은 반복이 생기게 된다.

 

그러므로 애초에 트리를 그릴 때 자식노드가 몇 개 인지 return을 해준다면 한번의 트리를 그림으로써 모든 노드의 자식의 수를 알 수 있게 된다.

 

이제 아래 그림을 통해 어떻게 진행되는지 알아보자

 

위 그림과 같은 트리가 있을 경우 트리를 그려가면서 자식의 수를 return해준다.

 

이때, 1은 자기 자신의 노드의 개수를 의미한다.

 

그러면 DFS(node) = 1+ DFS(자식 노드들) 과 같이 계산할 수 있게 된다.

 

이후 계산된 자식 노드들의 개수를 childs 배열에 저장한 뒤 Query가 들어올 때 마다 childs의 값을 return해주면 된다.

 

 

 

​

[아이디어 정리]

1. 루트 노드를 기준으로 트리를 그린다.
2. 트리를 그릴 때 자식노드의 수를 return 해주도록 DFS 함수를 만든다.
3. 그러면 자식의 수를 구하면서 트리를 그리는 함수를 다음과 같이 표현할 수 있다. DFS(node) = 1+DFS(자식 노드들)
4. 이후 계산한 자식노드들의 수를 childs 배열에 저장하고 Query가 들어올 때 마다 return 해준다. 

 

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int DFS(int rootN, vector<int> &par, vector<int>&childs, vector<vector<int>> &graph){
    int childsCnt=1;
    int tmpN;
    for (int i=0; i<graph[rootN].size(); i++){
        tmpN=graph[rootN][i];
        if (par[rootN]!=tmpN){
            par[tmpN]=rootN;
            childsCnt+=DFS(tmpN, par, childs, graph);
        }
    }
    childs[rootN]=childsCnt;
    return childsCnt;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int N,R,Q;
    cin>>N>>R>>Q;
    vector<int> par(N+1,0);
    vector<int> childs(N+1,0);
    vector<vector<int>> graph(N+1);
    int st,ed;
    for (int i=0; i<N-1; i++){
        cin>>st>>ed;
        graph[st].push_back(ed);
        graph[ed].push_back(st);
    }
    DFS(R,par,childs,graph);
    int tt;
    for (int i=0; i<Q; i++)
    {
        cin>>tt;
        cout<<childs[tt]<<"\n";
    }
    
}

 

---

밖에서 이 문제를 풀어서 C++ IDE가 없는 상태에서 코드만 작성해 문제를 풀었다...

다행히 복잡한 문제도 아니고 최근에 DP를 공부하고 있어서 IDE가 없어도 실수 없이 쉽게 풀 수 있었다.

 

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