백준 15681번 (java)

백준 15681번: 트리와 쿼리 java

관찰

서브트리의 크기를 빠르게 출력하는 방법 정점을 받아서 dfs를 돌려서 크기를 구할 수도 있겠지만 중복 문제가 많이 발생한다 값을 저장해주어서 입력받으면 바로바로 출력해주자!

정답코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int n, // 정점의 수
               r, // 루트의 번호
               q; // 쿼리의 수
    static List<Integer>[] edges; // 연결 리스트 트리
    static int[] res; // 정답을 저장
    static int[] visited; // dfs 도구
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        q = Integer.parseInt(st.nextToken());
        edges = new List[n+1];
        for(int i=1;i<n+1;i++){
            edges[i] = new ArrayList<Integer>();
        }
        res = new int[n+1];
        visited = new int[n+1];

        // 트리 연결
        for (int i = 0; i < n-1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[a].add(b);
            edges[b].add(a);
        }

        // dfs로 서브트리의 크기 구해줍시다
        dfs(r);

        for(int i = 0; i < q; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            sb.append(res[a]).append("\n");
        }
        System.out.println(sb.toString());
    }
    private static int dfs(int r) {
        visited[r] = 1;
        res[r] = 1; // 내 값은 1
        for(int next : edges[r]){
            if(visited[next] == 0){
                res[r] += dfs(next);
            }
        }
        return res[r];
    }
}

풀이

간선의 수가 정점의 수에 비해 많지 않아서 연결리스트로 트리를 구현해주었다!
그리고 dfs + 백트래킹을 통해 각 정점의 서브트리의 갯수를 구하여 저장

느낀점

dp를 한창 공부하다 보니 dp식 접근이 문제들을 풀 떄 굉장히 도움이 많이 되는 거 같다!