[BOJ] 백준 2668 - 숫자고르기 (자바)

DFS

풀었다. 하고 출처 봤는데 초등부 문제...... 초등학생들이 이런 문제를 푼단 말인가....?

나는 아주 단순하게 풀었다. 그래서인지 성능이 별로인거 같다.

풀이

1. 1~7까지 숫자가 있으므로 각 숫자마다 DFS() 를 해준다.

2. 사이클이 완성된다면 숫자 고르기 성공. 사이클이 실패면 위, 아래의 값이 달라지기 때문에 숫자를 고를 수 없다.

3. 단, 이전에 방문했던 점을 다시 방문하게 되면 무한재귀현상에 빠지게 된다. 그래서 이전에 방문했던 점들을 visited[] 배열로 체크해준다.

4. 1~7 숫자, 하나씩 DFS를 해준후 방문했던 점들 visited[] 배열을 초기화 시켜준다.

소스

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
 
public class Main {
    static int[] arr;
    static boolean[] visited;
    static int last;
    static ArrayList<Integer> list;
 
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
 
        int N = sc.nextInt();
        arr = new int[N + 1];
        visited = new boolean[N + 1];
        list = new ArrayList<Integer>();
        for (int i = 1; i <= N; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 1; i <= N; i++) {
            visited[i] = true;    //무한 재귀에 빠지면 안되므로 첫 시작점도 방문으로 체크
            last = i;
            DFS(i);
            visited[i] = false; //다음 숫자 DFS를 해야하므로 초기화 시켜준다.
        }
        Collections.sort(list);    // 작은수 부터 출력해야하므로 젖ㅇ렬
        System.out.println(list.size());
        for (int i : list) {
            System.out.println(i);    //list들을 하나씩 출력해준다.
        }
    }
 
    public static void DFS(int i) {
        
        if (!visited[arr[i]]) {     //이전에 방문한 점이 아니여야한다.
            visited[arr[i]] = true;     // 방문했으므로 true
            DFS(arr[i]);
            visited[arr[i]] = false; // 다음 DFS들을 위하여 false
        }
        if (arr[i] == last) {    //마지막 점이 출발점과 같다면 사이클이 완성됐으므로 리스트에 추가
            list.add(last);
        }
    }
}