[BOJ 2668] 숫자고르기 (Java, DFS)

 

---

문제 링크 

https://www.acmicpc.net/problem/2668

2668번: 숫자고르기

---

문제 풀이 위한 아이디어가 처음 생각나지 않았다. 텀프로젝트(BOJ 9466) 문제 풀이 후 동일하게 visit과 finish배열 활용하여 결과 값을 구할 수 있는 것을 이해하게 되었다. 

이런 기법을 어떻게 생각해내는지 대단하다 다들 :)

 

풀이 

- 사이클 발생하거나, 노드가 자신을 가르키는 경우를 구함
- 시간복잡도 : O(N)

- (기법*) finish 배열 활용하여 중복되는/이미 확인한 구간 탐색을 하지 않도록 함

1 -> 3 -> 1 -> 3 ..  
2 -> 1 -> 3 -> 1 ..

4 -> 5 -> 5
6 -> 4 -> 5 -> 5
7 -> 6 -> 4 -> 5 -> 5 

---

제출 코드

import java.util.*;
import java.io.*;

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int N;

    static int[] NUMBERS;

    static boolean[] visit, finish;

    static List<Integer> result = new ArrayList<>();

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        NUMBERS = new int[N + 1];
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            NUMBERS[i] = Integer.parseInt(st.nextToken());
        }

        visit = new boolean[N + 1];
        finish = new boolean[N + 1];

        br.close();
    }

    static void dfs(int x) {
        visit[x] = true;

        int y = NUMBERS[x];
        if(!visit[y]) {
            dfs(y);
        } else if(!finish[y]){
            while(x != y) {
                result.add(y);
                y = NUMBERS[y];
            }
            result.add(x);
        }

        finish[x] = true;
    }

    static void pro() {
        for(int i = 1; i <= N; i++) {
            if(!visit[i]) dfs(i);
        }

        Collections.sort(result);
        sb.append(result.size()).append("\n");
        for(int i : result) sb.append(i).append("\n");

        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}