백준 15681 트리와 쿼리 - JAVA

15681 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    private static List<List<Integer>> list = new ArrayList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();
        int[] qArray = new int[Q];
        boolean[] visit = new boolean[N+1];
        int[] children = new int[N+1];
        
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        } 
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            list.get(start).add(end);
            list.get(end).add(start);
        } 
        for (int i = 0; i < Q; i++) {
            qArray[i] = Integer.parseInt(br.readLine());
        } 
        dfs(R, visit, children);
        for (int i = 0; i < qArray.length; i++) {
            sb.append(children[qArray[i]]).append("\n");
        } 
        bw.write(sb.toString());
        bw.flush();
    }
    
    private static void dfs(int r, boolean[] visit, int[] children) {
        visit[r] = true;
        children[r]++;
        for (int i = 0; i < list.get(r).size(); i++) {
            int current = list.get(r).get(i);
            if (!visit[current]) {
                dfs(current, visit, children);
                children[r] += children[current];
            }
        } 
    }
}

 

알고리즘 설명

---

이 문제는 자식 노드를 가진 부모 노드가 그 자식 노드를 몇 개 가지고 있는지 묻는 문제입니다. DFS 알고리즘을 사용하여 각 노드별로 자식 노드를 찾는 것은 다른 문제들과 유사하지만, 해당 문제는 각 노드가 가진 자식 수를 계산하는 방법에 대해 고민해야 합니다. 재귀적으로 접근하면, 부모 노드는 그 자식들의 자식 수를 재귀적으로 확인하여 각 자식의 자식 수를 부모에게 더하는 방식으로 해결할 수 있습니다. DFS 문제에 어느 정도 익숙해지셨다면 어렵지 않게 풀 수 있는 문제였다고 생각합니다.”

 

코드 해석

---

트리의 정점 수 N, 루트 노드 R, 쿼리 수 Q를 입력받습니다. 문제에서 주어진 노드들의 연결은 트리 구조를 이루고 있으며, 트리의 간선 수는 정점 수에서 1을 뺀 값이므로, 총 N-1개의 간선 정보를 입력받습니다. 그런 다음, 쿼리에서 요구하는 노드들에 대해 그 노드를 루트로 하는 서브트리의 자식 노드 수를 구해야 합니다.

 

DFS 탐색을 통해 트리 구조를 순회하면서 각 노드가 가진 자식 노드들의 개수를 계산합니다. 트리 순회를 시작할 때, 루트 노드인 r도 노드의 개수에 포함해야하기 때문에 children[r]++로 루트 노드를 더해줍니다. 각 노드들의 자식 노드의 개수만을 세기위해 방문 여부를 체크하는 visit 배열을 사용하여 이미 방문한 노드는 다시 방문하지 않도록 처리합니다. 이렇게 하면 부모 노드가 이미 방문한 노드를 다시 세지 않도록 할 수 있습니다. 각 노드에 대해서는 자식 노드들의 자식 수를 누적하여 부모 노드의 자식 노드 개수에 반영됩니다. 탐색이 완료되면, children배열에서 쿼리에서 요구하는 노드를 루트노드로 하는 서브트리에 속한 정점의 수를 출력합니다.