[BOJ] 백준 15681. 트리와 쿼리

문제

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

 

 

 

 

 

---

풀이

 서브 트리에 속한 정점의 개수를 세는 문제입니다.

 

dfs를 통해 그래프를 탐색하며, 서브 트리의 루트가 인덱스인 배열에 정점의 개수를 저장합니다.

 

 처음에 문제를 풀이할 때, 루트가 아닌 제일 마지막 자식부터 dfs 탐색을 시작해보려고도 했지만, 그렇게 접근하면 마지막 자식도 체크해야하고, 방문 배열을 통해 접근을 막아주어야하고.. 여러모로 로직이 복잡해집니다.

 

 그래서 루트부터 출발해 자식으로 뻗어가며 subtrees 배열에 정점의 개수를 저장합니다. 이때 부모 노드에 자식 노드가 가진 정점의 개수를 더해주면 됩니다. 주의할 것은, 부모에서 자식으로 내려갔는데 다시 부모 노드를 검사하지 않도록 하는 것입니다. 이것은 dfs에 parent라는 매개 변수를 전달함으로써 조건을 걸어주었습니다.

 

 아래는 소스 코드입니다.

---

소스 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int N,R,Q;
    static ArrayList<Integer>[] list;
    static int[] subtrees;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        R = sc.nextInt();
        Q = sc.nextInt();

        list = new ArrayList[N+1];
        for(int i = 1;i<N+1;i++){
            list[i] = new ArrayList<>();
        }
        subtrees = new int[N+1];
        Arrays.fill(subtrees,1);

        for(int i = 0; i<N-1;i++){
            int st = sc.nextInt();
            int ed = sc.nextInt();
            list[st].add(ed);
            list[ed].add(st);
        }

        dfs(R,-1);

        for(int i = 0;i<Q;i++){
            int query = sc.nextInt();
            System.out.println(subtrees[query]);
        }
    }
    
    static void dfs(int now, int parent){
        for(int next:list[now]){
            if(parent!=next){
                dfs(next, now);
            }
        }
        if(parent!=-1) subtrees[parent]+=subtrees[now];
    }
}