[백준] 2668 숫자고르기 - JAVA

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

2668번: 숫자고르기

 

• 0번부터 시작하여 깊이 우선 탐색
• DFS 탐색 과정에서 사이클이 만들어지는지 확인
• 사이클이 만들어진다면, 사이클에 포함된 숫자 List에 add
• list 정렬 후, 출력
• 각 인덱스에 대응된 숫자는 하나이기 때문에 사이클이 겹칠 일은 없다.
• 아래 코드로 확인 

 

 

import java.util.*;
import java.io.*;

public class Main {
	static List<Integer> list = new ArrayList<>(); 
	static boolean[] visited; 
	static int[] arr; 
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		
		int N= Integer.parseInt(br.readLine());
		arr = new int[N]; 
		visited = new boolean[N]; 
        
		for(int i=0; i<N; i++) arr[i] = Integer.parseInt(br.readLine())-1;
		
		for(int i=0; i<N; i++) {
			find(i,arr[i]);
		}
		
		Collections.sort(list);
		System.out.println(list.size());
		for(int i : list) System.out.println(i+1);
	}
	private static void find(int start, int num) {
		if(start == num) { //dfs 시작과 같은 숫자 => 사이클
			list.add(num); 
			return; 
		}
		
		int next= arr[num]; 
		if(!visited[next]) {
			visited[next]= true;
			find(start, next); 
			visited[next]=false; 
		}
	}
	
}//end of class