[BOJ] 9466. 텀 프로젝트

DFS를 사용하는 문제지만 시간초과를 잘생각해야하는 문제이다.

일반적인 DFS를 사용한다면 시간초과가 쉽게 날수 있는 문제이다. 따라서 시간초과를 줄이기 위해 여러번 같은 노드를 방문하는 것을 주의 해야한다. 예를 들면 예제1번의 경우 1->3->3 이 나오고, 2->1->3->3 이 나온다. 2에서 시작한 경우 불필요하게 중복 방문을 하게 된다. 따라서 이런것을 해결해주기 위해 visit배열과 별개로 finished 배열을 만들어 노드에서 사이클을 이미 뽑아낸적이 있는 지를 체크해주었다. 또한, 탐색의 끝에 있는 노드는 항상 사이클을 형성 해주는 노드중에 하나 이므로 그 노드를 시작으로 다시 사이클을 체크해주는 방식을 사용하였다.

상당히 어려운 문제였다. 다시 풀어볼 필요가 있는 것 같다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

package study4;   import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer;   public class Main_bj_9466_텀프로젝트_un {          static boolean[] visit;     static boolean[] finished;     static int num;     static int[] next;     static int count;          public static void main(String[] args) throws Exception    {         BufferedReader br= new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = null;                  int T=Integer.parseInt(br.readLine());                  for(int tc=0;tc<T;tc++) {                          num=Integer.parseInt(br.readLine());             next=new int[num+1];             st=new StringTokenizer(br.readLine());                          for(int i=1;i<=num;i++) {                 next[i]=Integer.parseInt(st.nextToken());             }                          visit =new boolean[num+1];             finished=new boolean[num+1];             count=0;             for(int i=1;i<=num;i++) {                 if(visit[i]==false)                     dfs(i);             }                                       System.out.println(num-count);         }     }          static void dfs(int i) {         visit[i]=true;                  int nextI = next[i];                  if(visit[nextI]==false) {             dfs(nextI);         }else {             if(finished[nextI]==false) {                 count+=1;                                  for(int j=nextI; j!=i ; j=next[j]) {                     count+=1;                 }             }         }         finished[i]=true;     } }   Colored by Color Scripter

package study4;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main_bj_9466_텀프로젝트 {
    
    static boolean[] visit;
    static boolean[] finished;
    static int num;
    static int[] next;
    static int count;
    
    public static void main(String[] args) throws Exception    {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int T=Integer.parseInt(br.readLine());
        
        for(int tc=0;tc<T;tc++) {
            
            num=Integer.parseInt(br.readLine());
            next=new int[num+1];
            st=new StringTokenizer(br.readLine());
            
            for(int i=1;i<=num;i++) {
                next[i]=Integer.parseInt(st.nextToken());
            }
            
            visit =new boolean[num+1];
            finished=new boolean[num+1];
            count=0;
            for(int i=1;i<=num;i++) {
                if(visit[i]==false)
                    dfs(i);
            }
            
            
            System.out.println(num-count);
        }
    }
    
    static void dfs(int i) {
        visit[i]=true;
        
        int nextI = next[i];
        
        if(visit[nextI]==false) {
            dfs(nextI);
        }else {
            if(finished[nextI]==false) {
                int prev=nextI;
                while(true) {
                    count+=1;
                    if(prev == i)
                        break;
                    prev=next[prev];
                }
                    
//                count+=1;
//                for(int j=nextI; j!=i ; j=next[j]) {
//                    count+=1;
//                }
            }
        }
        finished[i]=true;
    }
}