[JAVA] BOJ 백준 15681번 - 트리와 쿼리

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

문제를 보고 쉽겠다고 생각해서 연결리스트로 각 노드들의 자식들을 저장해 놓는 방식을 채택했더니 메모리 초과가 떴다.

그래서 그냥 배열 하나로 끝내는 방법이 있을 것 같아서 고민하다가 DP 알고리즘를 이용해 자식 노드들의 하위 자식들을 먼저 채워 넣은 후에 루트 노드까지 카운팅되도록 코드를 짰다.

public static int parentDFS (List<Integer>[] list, int v, int[] parent) {
    parent[v] = 1;

    for (Integer i : list[v]) {
        if (parent[i] == 0) {
            parent[v] += parentDFS(list, i, parent);
        }
    }

    return parent[v];
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B15681.java

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

class Main {
    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());

        List<Integer>[] list = new ArrayList[N+1];

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

        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            list[v1].add(v2);
            list[v2].add(v1);
        }

        int[] parent = new int[N+1];
        parentDFS(list, R, parent);

        for (int i = 0; i < Q; i++) {
            int search = Integer.parseInt(br.readLine());
            bw.write(parent[search]+"\n");
        }

        br.close();
        bw.flush();
        bw.close();
    }

    public static int parentDFS (List<Integer>[] list, int v, int[] parent) {
        parent[v] = 1;

        for (Integer i : list[v]) {
            if (parent[i] == 0) {
                parent[v] += parentDFS(list, i, parent);
            }
        }

        return parent[v];
    }
}

---

4. 결과 및 회고

너무 간단한 문제라 블로그 포스팅을 할까 말까 고민했는데, 코테 문제를 풀 때 입력값을 보면서 메모리 사용량에 대한 고민도 앞으로는 해야 할 것 같아서 작성했다. 한번에 제대로 풀 수 있도록 노력하장.