숫자고르기
백준 2668: 숫자고르기
풀이
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);
}
}