알고리즘 모음(C++)

백준 15681 - 트리와 쿼리(C++) 본문

백준

백준 15681 - 트리와 쿼리(C++)

공대생의 잡다한 사전 2023. 8. 1. 22:58

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

 

15681번: 트리와 쿼리

트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)

www.acmicpc.net

트리가 주어졌을 때, 쿼리를 기준으로 자신을 포함한 자식노드의 개수를 구하는 문제입니다.

 

루트노드는 주어졌기 때문에 루트노드부터 시작해 자식의 개수를 찾으면 됩니다.

 

간선을 저장할 때, 양뱡향으로 저장하기에 부모와 자식 노드의 구분은

이전에 방문을 했는지 여부를 저장하는 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