[백준 9466] 텀 프로젝트 (Java)

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

9466번: 텀 프로젝트

접근 방법

일반적인 DFS로 접근하여 시도를 했는데 런타임 에러가 발생했다.

1
5
2 3 4 5 4

위 케이스와 같이 5 -> 4 -> 5 -> 4 ... 의 경우 overflow 에러가 발생하면서 런타임에러가 일어나는 것이 문제가 되었다.

 

구현한 코드를 싹 갈아엎고 처음부터 다시 짰다. (알고리즘 마스터의 길은 멀고도 험하다...)

방문했는지 여부를 확인하는 isVisted 배열과 함께

팀 배정 결과를 담는 isDone 배열을 더 추가하였다.

 

문제에서 주어진 케이스를 예시로 들어보면

4, 7, 6 이 한 팀을 이루게 되는데

dfs(4)를 시도함으로써 이미 dfs(7), dfs(6)의 결과까지 도출하기 때문에

main에서 이미 팀 배정 결과가 나온 index는 탐색하지 않아도 됨을 표시해야 시간을 절약할 수 있다.

시간 효율 처리를 위해서 isDone 배열을 하나 더 사용하는 것이다.

[참고] https://geehye.github.io/baekjoon-9466/#

 

소스 코드

package beckjoon;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class BaekJoon9466 {
    private static int T;
    private static int n;
    private static int[] students;
    private static boolean[] isVisited;
    private static boolean[] isDone;
    private static int count;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        T = scanner.nextInt();

        StringBuilder stringBuilder = new StringBuilder();
        List<Integer> numbers = new ArrayList<>();

        for (int j = 0; j < T; j++) {
            n = scanner.nextInt();
            numbers.clear();

            students = new int[n + 1];
            isVisited = new boolean[n + 1];
            isDone = new boolean[n + 1];
            count = 0;

            for (int i = 1; i <= n; i++) {
                students[i] = scanner.nextInt();
            }


            for (int i = 1; i <= n; i++) {
                if (!isDone[i]) {
                    dfs(i);
                }
            }

            stringBuilder.append(n - count);
            stringBuilder.append("\n");
        }

        System.out.println(stringBuilder.toString().trim());
    }

    private static void dfs(int now) {
        if (isVisited[now]) {
            isDone[now] = true;
            count++;
        } else {
            isVisited[now] = true;
        }

        int next = students[now];

        if (!isDone[next]) {
            dfs(next);
        }

        isVisited[now] = false;
        isDone[now] = true;
    }
}