숫자고르기


백준 2668: 숫자고르기

문제보기
Alt text

풀이

visited 방문배열은 전체적인 방문 여부를 확인하는 것이고,
check 방문배열은 한 번의 사이클에서 방문 여부를 확인하기 위한 것.

소스코드

import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	static int[] arr;
	static int N;
	static LinkedList<Integer> list;
	static boolean[] visited;
	static boolean[] check;
	static int start;
	static LinkedList<Integer> ans;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		arr = new int[N + 1];
		visited = new boolean[N + 1];
		
		for (int i = 1; i <= N; i++) {
			arr[i] = sc.nextInt();
		}
		ans = new LinkedList<>();
		for (int i = 1; i <= N; i++) {
			if (visited[i])
				continue;
			check = new boolean[N+1];
			list = new LinkedList<>();
			start = i;
			dfs(i);
		}
		
		Collections.sort(ans);
		System.out.println(ans.size());
		for(int i=0; i<ans.size(); i++)
			System.out.println(ans.get(i));
	}
	
	static void dfs(int idx) {
		check[idx] = true;
		list.add(idx);
		int n = arr[idx];

		//무한루프를 만들지 않기 위해 check배열로 방문 확인.
		if(check[n]) {
			if(n==start) {
				for (int i = 0; i < list.size(); i++) {
					ans.add(list.get(i));
					visited[list.get(i)] = true;
				}
			}
			return;
		}
		
		if (!check[n]&&visited[n]) {
			// 이미 방문했던 곳은 방문배열 체크 후 리턴.
			// 방문 체크 시, start만 방문체크 해주기.
			visited[start] = true;
			return;
		}
		
		if (!check[n]&&n == start) {
			// 리스트에 담긴 집합 일치->정답리스트에 담아주고 + 방문배열 체크 후 리턴.
			// 방문 체크 시, 리스트에 담긴 모든 수 방문체크
			for (int i = 0; i < list.size(); i++) {
				ans.add(list.get(i));
				visited[list.get(i)] = true;
			}
			return;
		}

		if(!check[n]&&idx==n) {
			//n과 start가 같았다면 위의 if문에서 걸려졌으므로 여기서는 집합 불일치.
			visited[start] = true;
			return;
		}
		dfs(n);
	}
}