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

9466번: 텀 프로젝트

시간 초과와의 싸움이었다.

N번만큼 for문을 돌면서 visited 배열을 초기화해줬는데

이게 시간 초과의 주된 원인이라고 한다.

그래서 초기화는 테스트 케이스마다 한 번씩만 해주고

재귀에서 빠져나올 때마다 visited 배열의 값을 false로 바꿔주는 방식으로 대체하였다.

 

<Key Point>

1. 각 원소는 무조건 어떤 원소를 가리킨다.

마지막엔 무조건 사이클로 끝나게 된다.

 

2. 한 번 방문한 곳은 visited, 예전에 검사가 끝난 곳은 done으로 표시할 때,

done으로 표시되어 있으면

예전에 검사가 끝난 원소라서 더 이상 들어갈 필요가 없어 return 한다.

 

done은 아닌데 visited로 표시되어 있으면

아까 방문했던 곳을 재방문했다는 것이다.

→ 사이클이므로 res에 + 1 해주고 done으로 표시해준다.

 

done도 아니고 visited도 아니면

처음 방문하는 곳이므로 visited 표시만 해주고 재귀로 더 들어가 본다.

 

사이클인 애들은 재방문하면서 done 표시를 하지만

사이클이 아니라서 못 해준 애들을 위해

재귀에서 빠져나오면 done으로 표시를 해준다.

 

이렇게 사이클이든 아니든 검사가 완료된 애들을 done으로 표시해 주어야

불필요한 계산을 막아주어 시간 초과가 나지 않는다.

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

public class BOJ_9466_텀프로젝트 {
	private static int T, N, res;
	private static int arr[];
	private static boolean visited[], done[];
	
	public static void dfs(int idx) {
		if(done[idx]) return; // 이전에 이미 검사했다는 뜻이므로 더 이상 들어갈 필요가 없다.
		if(visited[idx]) { // 방문을 했었다 == 사이클 구성원이다
			done[idx] = true; // 이제 다시 볼 일 없으므로 done 체크
			res++; // 사이클 구성원이므로 + 1
		}
		visited[idx] = true; // 방문 체크
		dfs(arr[idx]);
		done[idx] = true; // 사이클이 아닌 애들도 검사 끝났으니까 done 체크
		visited[idx] = false; // 방문 체크한 거 초기화
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			N = Integer.parseInt(br.readLine()); res = 0;
			arr = new int[N + 1]; done = new boolean[N + 1]; visited = new boolean[N + 1];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int n = 1; n <= N; n++) arr[n] = Integer.parseInt(st.nextToken());
			
			for(int i = 1; i <= N; i++) {
				if(done[i]) continue; // 이미 검사한 애들은 스킵한다.
				dfs(i);
			}
			System.out.println(N - res); // 사이클에 해당하지 않는 학생 수 출력
		}
	}
}