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

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

2668번: 숫자고르기

 

문제해설

DFS 문제입니다.

각 사이클을 구할떄 DFS를 통해서 계속해서 파고 들어가다가 해당 인덱스가 다시 나오면 사이클이 발생했다고 판단하면 되는 문제입니다.

헷갈리는 문제였습니다.

 

코드

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

public class Main {
	public static int N;
	public static int[][] map;
	public static boolean[] visited;
	public static ArrayList<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	map = new int[2][N+1];
    	visited = new boolean[N+1];
    	for(int i=1;i<=N;i++) {
    		map[0][i] = i;
    		map[1][i] = Integer.parseInt(br.readLine());
    	}
    	
    	for(int i=1;i<=N;i++) {
    		visited[i] = true;
    		DFS(i, i);
    		visited[i] = false;
    	}
    	
//    	Collections.sort(list); 어처피 map[0][N+1] 은 모두 1 2 3 4 5 6 7 .. 이렇게 오름차순 되어있으므로 Sort를 안해도됩니다.
    	System.out.println(list.size());
    	for(int i = 0;i<list.size();i++) {
    		System.out.println(list.get(i));
    	}
    	
    } 
    
    public static void DFS(int start, int target) {
    	if(visited[ map[1][start] ] == false) {
    		visited[ map[1][start]] = true;
    		DFS( map[1][start] , target);
    		visited[ map[1][start]] = false;
    	}
    	if(map[1][start] == target) list.add(target);
    }
    
    
}