[BOJ] 2668. 숫자고르기

그래프의 사이클을 찾는 문제이다.

DFS를 이용하여 그래프의 사이클을 찾아서 pq에 저장하였다. DFS를 이용하여 그래프의 cycle을 찾을때는 visit 배열 뿐만 아니라 finished 배열을 하나 더 사용해준다. finished를 이용하여 이미 완전히 탐색이 끝났는지를 확인해주었다. DFS를 도는중 만일 visit가 true이지만 finished가 false 인곳을 찾는다면 cycle을 찾은 조건을 만족한다.

package study4;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
 
public class Main_bj_2668_숫자고르기 {
    static int N;
    static boolean[] visit;
    static boolean[] finished;
    static int[] next;
    static PriorityQueue<Integer> pq;
     
    
    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        next=new int[N+1];
        visit=new boolean[N+1];
        finished=new boolean[N+1];
        pq=new PriorityQueue<>();
        
        for(int i=1;i<=N;i++) {
            next[i]=Integer.parseInt(br.readLine());
        }
        
        for(int i=1;i<=N;i++) {
            if(visit[i]==false)
                dfs(i);
        }
        
        System.out.println(pq.size());
        while(!pq.isEmpty())
            System.out.println(pq.poll());
    }
    
    static void dfs(int i) {
        visit[i]=true;
        
        int nextI=next[i];
        
        if(visit[nextI]==false) {
            dfs(nextI);
        }else {        
            if(finished[nextI]==false) {    //방문은 했지만 끝나지 않음 -> 사이클이 있는 경우
                int find=nextI;
                
                while(true) {
                    pq.add(find);
                    if(find==i)
                        break;
                    find=next[find];
                }
                
            }
        }
        
        finished[i]=true;
    }
}