[백준][Java] 12524 - Twibet (Large)

목차

문제 정보

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

12524번: Twibet (Large)

난이도 : S2

유형 : DFS, BFS

---

문제 풀이

수도승과 추종자들을 단방향 간선으로 연결시켜 준다.

그리고 수도승마다 DFS 탐색을 통해 자신을 포함하여 연결된 추종자들을 수를  세어주면 된다.

---

코드

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

/**
 * BOJ - 12524
 * author - devteo77
 */

public class Main {

    int T;
    int N;
    ArrayList<Integer>[] edges;
    boolean[] isVisited;

    public int execDFS(int node) {
        int res = 1;

        for (int next : edges[node]) {
            if (!isVisited[next]) {
                isVisited[next] = true;
                res += execDFS(next);
            }
        }

        return res;
    }

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());
        int tc = 1;
        while (T-- > 0) {
            N = Integer.parseInt(br.readLine());
            edges = new ArrayList[N + 1];
            for (int i = 1; i <= N; i++) {
                edges[i] = new ArrayList<>();
            }

            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                edges[Integer.parseInt(st.nextToken())].add(i);
            }


            sb.append("Case #").append(tc++).append(":\n");
            for (int i = 1; i <= N; i++) {
                isVisited = new boolean[N + 1];
                isVisited[i] = true;
                sb.append(execDFS(i)).append('\n');
            }
        }

        System.out.print(sb);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}