[백준] 2668번:숫자고르기(Java 자바)

문제

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

2668번: 숫자고르기

 

 

풀이 및 소스코드

 

1 -> 3 -> 1

시작했던 숫자로 다시 돌아오는 지 여부를 dfs로 확인해 준 후, 확인이 되면 결과값 리스트에 담아주면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
	static int n, num;
	static int[] arr;
	static List<Integer> res;
	static boolean[] c;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        c = new boolean[n];
        arr = new int[n];
        for(int i=0;i<n;i++) {
        	arr[i] = Integer.parseInt(br.readLine())-1;
        }
        res = new LinkedList<Integer>(); // 결과값 담을 리스트
        
        for (int i=0;i<n;i++) {
        	c[i] = true;
        	num = i;
        	dfs(i);
        	c[i] = false;
        }
        
        Collections.sort(res);
        System.out.println(res.size());
        for(Integer x:res) {
        	System.out.println(x+1);
        }
    }
    
    public static void dfs(int i) {
    	if(arr[i]==num) res.add(num); // 시작했던 수와 arr[i]가 같아진다면 결과에 담기
    	
    	if(!c[arr[i]]) {
    		c[arr[i]] = true;
    		dfs(arr[i]);
    		c[arr[i]]=false;
    	}
    }
}