백준 2668번 숫자고르기

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


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

        dfs(arr[start],init,visited);

    }
}

풀이방법

📢이문제의 핵심은 뽑은 숫자들이 싸이클을 돌 경우만 고를수 있다.
즉, 마지막에 뽑은 숫자가 결국 처음에 뽑은 숫자와 같은 경우를 뜻한다.
또한, 이때 해당하는 싸이클 전체를 저장하는것이 아니라, 처음 뽑은 그 숫자만 저장하고 다음탐색을 시작한다.

1. 숫자를 하나씩 dfs탐색시킨다.
2. 해당 인덱스의 숫자가 다음 인덱스가 되도록 dfs를 설계한다.
3. 결국 처음 숫자로 돌아오면 그 숫자를 list에 넣는다.
4. list크기와 list를 출력한다.

후기

숫자들이 싸이클을 돌 경우를 뜻한다는 거는 이해가 간다.
근데 겹치는 경우를 어떻게 중복제거 하는지 도저히 모르겠다.
풀이는 애초에 중복되지 않게 싸이클의 시작 숫자만 리스트에 넣는데,
이거를 떠올릴수가 있는건가..? 어떻게 해서 저런 생각을 할 수있는거지..