[백준] 9466 텀 프로젝트 - DFS + 아이디어 + 시간초과 JAVA

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

9466번: 텀 프로젝트

문제풀이

DFS 문제였습니다.

문제조건에

- T

- n (2 ≤ n ≤ 100,000)

일반 BFS로 모든 경우를 다 돌면서 처리를 할경우 O(N^2) 으로  T * (100,000) * (100,000) 으로 최악의 경우에 100억 * T 의 시간이 걸립니다.

 

 

그렇기에 Visited 방문 배열과 CycleFinished 사이클을 경험 배열을 선언하여

, CycleFinished를 경험했다면 DFS 자체를 돌지 못하게 처리함으로써 시간초과를 줄일 수 있습니다.

또한, 그 와중에 방문처리는 초기화 시킴으로써, 사이클 검사를 올바르게 할 수 있도록 처리해야합니다.

 

자세한 설명은 주석처리해두었습니다.

 

코드

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

public class Main {
	public static int T, N, count= 0;
	public static int[] map;
	public static boolean[] visited, cyclefinished;
	public static int result = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	T = Integer.parseInt(st.nextToken());
    	
    	while(T > 0) {
	       	N = Integer.parseInt(br.readLine());
	     	map = new int[N+1];
	     	visited = new boolean[N+1];
	     	cyclefinished = new boolean[N+1];
	     	count = 0;

     		st = new StringTokenizer(br.readLine());
	     	for(int i=1;i<=N;i++) {
     			map[i] = Integer.parseInt(st.nextToken());
	     	}
	     	
	     	for(int i=1; i<=N;i++) {
	     		if(cyclefinished[i]) continue;  //사이클을 한번이라도 검사에 넣었는데 실패햇다면 사이클이 불가능함
	     		DFS(i);
	     	}
	     	T--;
	     	System.out.println(N - count);
    	}

    	
    }
    
    public static void DFS(int now) {
    	if(visited[now]) { //Cycle에서 두번쨰 방문이라면 이미 Cycle 에 포함되었음
    		cyclefinished[now] = true; //Cycle 검사가 끝남
    		count++; //Cycle에 포함되었으므로  count++
    	}
    	else if(visited[now] == false){ //첫방문인경우
    		visited[now] = true; //방문처리
    	}
    	
    	int next = map[now];
    	if(!cyclefinished[next]) { //아직 Cycle 검사가 안끝났다면 계속해서 DFS를 들어갑니다.
    		DFS(next);
    	}
    	
    	visited[now] = false; //방문처리를 종료
    	cyclefinished[now] = true; //만약 사이클에 들어가지 않았다면 더이상 사이클검사를 해도 의미가 없으므로 사이클을 했다는 flag가 남겨져있다고 처리
    	
    }
    
}