[백준-2668]-[DFS]-숫자고르기

문제링크 : https://www.acmicpc.net/problem/2668

---

이 문제는 사이클이 발생할 때 까지 DFS로 탐색을 진행하면 된다. 

만약 사이클이 발생하지 않는다면 visited 정보를 초기화 해주고 사이클이 발생했다면 방문 정보는 초기화 하지 않아야 된다. 

1	2	3	4	5	6	7
3	1	1	5	5	4	6

예제로 받은 데이터로 표를 만들면 위의 표와 같은데 여기서 1을 탐색하면 1의 값이 3 이고 인덱스 3의 값을 탐색한다.

인덱스 3의 값은 1이고 1과 3은 사이클을 돌게 된다. 

사이클이 발생하면 visited는 초기화 하지 않는다. 

1	2	3	4	5	6	7
3	1	1	5	5	4	6

2번 인덱스의 값은 1인데 1은 이미 방문 했으므로 사이클이 성립 안된다. 2의 visited는 초기화 해주고 다음 인덱스를 확인한다.

1	2	3	4	5	6	7
3	1	1	5	5	4	6

인덱스 3은 방문 했으므로 넘어가고 인덱스 4의 값은 5이고 인덱스 5로 넘어와 인덱스 5의 값을 보면 5 인데 여기서는 시작 인덱스 4와 사이클이 발생하지 않기에

4 5 의 visited는 초기화 한다.

1	2	3	4	5	6	7
3	1	1	5	5	4	6

이제 시작인덱스는 5이고 인덱스 5의 값은 5이므로 사이클이 발생했다. 5의 visited 정보는 초기화 하지 않고 다음 인덱스로 넘어간다.

1	2	3	4	5	6	7
3	1	1	5	5	4	6

다음 시작인덱스는 6이고 인덱스 6의 값은 4  인덱스 4의 값은 5

하지만 인덱스 5는 이미 방문했으므로 그 다음으로 진행 할수 없기에 DFS 탐색은 종료하고 방문 정보를 다시 초기화 한다.

다음 인덱스 7도 같은 방법으로 탐색을 하고 DFS 탐색은 종료하면서 모든 인덱스를 탐색했고

visited 정보가 아직 남아 있는 인덱스들이 집합을 이루고 있다

이 값들만 출력 해주면 요구하는 답을 도출해 낼 수 있다. 

이 문제를 정리하기 위해 다른 사람들의 소스를 찾아봤는데  정말 다양한 방법으로 문제를 풀어서 이 방법이 맞다 틀리다 말할 수는 없을거 같다.

이문제는 DFS로 문제를 푸는거고 DFS로 풀었다면 되는거라고 생각한다.

나는 사이클이 발생하면 DFS에서 참을 반환하고 결국엔 사이클이 발생하지 않고 DFS 탐색이 마무리 되면 거짓을 반환하게 작성했다.

DFS를 돌면서 접근한 인덱스는 큐에 저장하였고 DFS 탐색의 반환 결과가 거짓이면 큐에 있는 모든 인덱스들의 방문 기록을 초기화 시켜줬다.

소스

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
 
public class Main {
    public static int size;
    public static int res;
    public static boolean[] visited;
    public static int[] arr;
    public static int[] ans;
    public static PriorityQueue<Integer> pq;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        size = Integer.parseInt(br.readLine());
        arr = new int[size+1];
        ans = new int[size+1];
        
        for(int i=1; i <= size; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        visited = new boolean[size+1];
        
        for(int i=1; i <= size; i++) {
            pq = new PriorityQueue<Integer>();
            if(!visited[i]) {
                if(!dfs(i, i, 1)) {
                    while(!pq.isEmpty()) {
                        visited[pq.poll()] = false;
                    }
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        sb.append(res + "\n");
        
        for(int i=1; i <= size; i++) {
            if(visited[i]) sb.append(i + " ");
        }
        
        bw.write(sb.toString());
        
        br.close();
        bw.close();
    }
    
    public static boolean dfs(int startIdx, int idx, int cnt) {
        visited[idx] = true;
        pq.offer(idx);
        
        int nextIdx = arr[idx];
        
        if(startIdx == nextIdx) {
            res += cnt;
            return true;
        }
        if(!visited[nextIdx]) {
            return dfs(startIdx, nextIdx, cnt+1);
        }
        return false;
    }
}