Notice
Recent Posts
Recent Comments
Link
알고리즘 모음(C++)
백준 15681 - 트리와 쿼리(C++) 본문
문제 링크입니다. https://www.acmicpc.net/problem/15681
트리가 주어졌을 때, 쿼리를 기준으로 자신을 포함한 자식노드의 개수를 구하는 문제입니다.
루트노드는 주어졌기 때문에 루트노드부터 시작해 자식의 개수를 찾으면 됩니다.
간선을 저장할 때, 양뱡향으로 저장하기에 부모와 자식 노드의 구분은
이전에 방문을 했는지 여부를 저장하는 check 배열을 통해 했습니다.
자식노드일 경우 이미 부모노드는 탐색을 했을 것이기에 check 배열의 값은 0이 아닐 것입니다.
이를 통해 자식과 부모를 나눌 수 있습니다.
자세한 것은 코드를 참고해주세요.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#define INF 987654321
using namespace std;
int N, R, Q;
vector<int> connect[100001];
int Size[100001];
int check[100001];
void count_subtree_node(int x){
Size[x] = 1;
check[x] = 1;
for(int i = 0; i < connect[x].size(); i++){
int xx = connect[x][i];
if(check[xx] == 1) continue;
count_subtree_node(xx);
Size[x] += Size[xx];
}
}
void solve(){
count_subtree_node(R);
for(int i = 1; i <= Q; i++){
int x;
cin >> x;
cout << Size[x] << "\n";
}
}
int main(){
cin.tie(0);
cout.tie(0);
cin >> N >> R >> Q;
for(int i = 1; i < N; i++){
int x, y;
cin >> x >> y;
connect[x].push_back(y);
connect[y].push_back(x);
}
solve();
return 0;
}
질문 및 조언은 댓글을 남겨주세요.
'백준' 카테고리의 다른 글
백준 5557 - 1학년(C++) (0) | 2023.08.07 |
---|---|
백준 9184 - 신나는 함수 실행(C++) (0) | 2023.08.01 |
백준 2240 - 자두나무(C++) (0) | 2023.07.31 |
백준 4811 - 알약(C++) (0) | 2023.07.31 |
백준 10164 - 격자상의 경로(C++) (0) | 2023.07.27 |