BOJ (Java) 9466번: 텀 프로젝트

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

---

풀이

처음에는 해당 학생이 팀을 가지고 있는지를 확인하고, 없다면 다시 방문하는 식으로 작성했다.

이 경우 이미 탐색을 했음에도 다시 탐색해야 하고 이로 인한 방문 체크 배열을 초기화 하는 과정까지 포함되어 시간초과가 발생했다.

 

 

모르겠어서 다른 풀이를 봤다.

 

visited, finished 배열을 사용해 각각 방문 여부와 현재 탐색하는 사이클이 끝난 여부를 저장했다.

방문했지만 아직 사이클이 끝나지 않았다면, 이는 (출발점과 도착점이 동일 여부와 관계없이) 내부에 다른 사이클이 존재하는 것이므로 해당 사이클 내의 노드의 개수를 세어준다.

해당 사이클을 다 탐색했다면 그 사이클 탐색을 완료했다고 표시해주면, 그 사이클에 있는 학생들은 더 이상 방문하지 않아도 되므로 배열 초기화 과정이 없어져 시간 초과를 해결할 수 있었다.

 

알고리즘은 언제까지 해야 이런 거 잘 풀 수 있을까ㅠ

---

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    private static int T, N;
    private static int[] choices;
    private static boolean[] finished;
    private static boolean[] visited;
    private static int count;

    public static void main(String[] args) throws IOException {
        // input
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(bf.readLine());

        for (int i = 0; i < T; i++) {
            N = Integer.parseInt(bf.readLine());

            finished = new boolean[N];
            visited = new boolean[N];

            choices = new int[N];
            String[] inputs = bf.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                choices[j] = Integer.parseInt(inputs[j]) - 1;
            }

            // 팀이 없는 학생들의 팀 찾기
            count = 0;
            for (int j = 0; j < N; j++) {
                if (!visited[j]) {
                    makeTeam(j);
                }
            }
            System.out.println(N - count);
        }
    }

    private static void makeTeam(int now) {
        visited[now] = true;

        int next = choices[now];
        if (!visited[next]) {
            makeTeam(next);
        } else if (!finished[next]) {
            for (int i = next; i != now; i = choices[i]) {
                count++;
            }
            count++; // now 자신 포함
        }
        finished[now] = true;
    }
}