<그래프> BOJ 15681 트리와 쿼리

문제

임의의 루트 있는 트리의 간선 정보가 주어질 때 정점을 주면 정점을 루트로 하는 서브 트리에 포함된 정점의 개수를 구하는 문제입니다.

접근

1. dfs를 사용할건데요. dfs를 작성할때 일반적으로는 check 배열이나 visited 배열을 사용해서 방문한 정점을 체크하실텐데요. 트리에서는 check배열없이도 dfs를 진행할 수 있습니다. 그 이유는 트리에서 한 정점 u에 다른 정점 v로 부터 왔다고 했을 때 그 v정점에 다시 방문하지 않는다면 모든 정점에는 딱 한번만 방문하게 됩니다.

• 트리의 특징
  • 임의의 두 정점 u와 v에 대해 단순 경로는 유일하다
  • 사이클이 없는 무방향 연결 그래프이다.
  • 간선의 개수가 정점의 개수보다 하나 작다.

2. 1번의 코드를 살펴보면 아래와 같습니다. check배열이 없기 때문에 코드도 매우 간결합니다.

    static void dfs(int now, int before) {
        for (int next : list[now]) {
            if (next == before)
                continue;
            dfs(next, now);
        }
    }
    
    dfs(root,root);

3. 위와 같이 dfs를 진행한다고 했을 때 sub트리에 포함된 정점을 구하기 위해서 정점의 개수를 길이로 하는 배열을 하나 만들겠습니다. 이 배열을 sub배열이라고 할게요. dfs에서 now 정점을 시작으로 before를 제외한 now정점과 연결된 모든 정점을 방문할텐데요.이 과정에서 점화식을 세워보면
   $sub[now] = 1 +\sum sub[next]$가 됩니다. 1은 now정점 자기자신을 포함하기 위해 더해주었습니다.

코드(JAVA)

import java.io.*;
import java.util.*;

class baek__15681 {
    static ArrayList<Integer>[] list;
    static int[] sub = new int[100001];

    static void dfs(int now, int before) {
        sub[now] += 1;
        for (int next : list[now]) {
            if (next == before)
                continue;
            dfs(next, now);
            sub[now] += sub[next];
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] temp = br.readLine().split(" ");

        int n = Integer.parseInt(temp[0]);
        int r = Integer.parseInt(temp[1]);
        int q = Integer.parseInt(temp[2]);

        list = new ArrayList[n + 1];

        for (int i = 0; i < n + 1; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            temp = br.readLine().split(" ");
            int u = Integer.parseInt(temp[0]);
            int v = Integer.parseInt(temp[1]);

            list[u].add(v);
            list[v].add(u);
        }

        dfs(r, r);

        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            int qq = Integer.parseInt(br.readLine());
            sb.append(sub[qq] + "\n");
        }

        System.out.print(sb);

    }
}