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

안녕하세요.

오늘은 숫자고르기 문제를 풀어보도록 하겠습니다.

 

 

📌 접근

원소를 순회할 때 사이클이 만들어진다면, 조건에 만족하는 수가 된다.

 

ex1) 1 을 뽑을 수 있는지 ?

1 -> 3 (arr[1]) -> 1 (arr[3]) -- 사이틀 발생 O

 

ex2) 2 를 뽑을 수 있는지 ?
2 -> 1 (arr[2]) -> 3 (arr[1]) -> 1 (arr[3]) -- 사이클 발생 X

 

만약 조건을 만족하는 수라면, 리스트에 넣는다.

최종 리스트를 오름차순 정렬하면 정답을 구할 수 있다.

💻 풀이

// hyeblee
import java.io.*;
import java.util.*;


public class Main {
	public static int N;
	public static int[] line2;
	public static boolean[] visited;
	public static List<Integer> list = new ArrayList<>();
	
	public static void dfs(int start, int target) {
		if(line2[start]==target) {
			list.add(target);
			return;
		}
		start = line2[start];
		
		if(!visited[start]) {
			visited[start] = true;
			dfs(start,target);
			visited[start] = false;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		line2 = new int[N+1];
		visited = new boolean[N+1];
		
		for(int i=1;i<=N;i++) {
			line2[i] = Integer.parseInt(br.readLine());
		}
		
		for(int i=1;i<=N;i++) {
			visited[i] = true;
			dfs(i, i);
			Arrays.fill(visited, false);
		}
		
		Collections.sort(list);
		System.out.println(list.size());
		for(int n: list) {
			System.out.println(n);
		}
	}
}

🤔 고민했던 점 & 어려웠던 부분

 

처음에 dfs이고, 재귀를 사용해야한다고 생각했습니다.

하지만 어떤 방식으로 재귀를 돌려야할지 감이 오지 않아서 다른 사람의 풀이를 참고했습니다.