[백준]2668번. 숫자 고르기(JAVA)

문제

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

---

풀이

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

public class Main {


    static int n;
    static int[] origin;
    static int[] in;
    static boolean[] visited;
    static Set<Integer> answer = new TreeSet<>(); // 중복 처리와 오름차순 출력을 위한 TreeSet선언

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        origin = new int[n]; // n개의 칸 입력
        in = new int[n]; // n개의 정수 입력 저장할 배열
        visited = new boolean[n]; // 방문 처리를 위한 배열

        for (int i = 0; i < n; i++) {
            origin[i] = i+1; // 기본 배열을 idx+1 해서 저장
            in[i] = Integer.parseInt(br.readLine()); // 입력받은 값 저장
            if(i+1 == in[i]){ // 만약 입력 시점부터 같은 값이 들어온다면
                answer.add(i+1); // 정답이기 때문에 리스트에 추가하기
                visited[i] = true; // 이 곳은 방문할 필요가 없음을 선언
            }
        }
        for(int i = 0; i < n; i++){
            dfs(i, i+1, new ArrayList<>()); // 모든 인덱스에 대한 dfs 적용
        }

        System.out.println(answer.size()); // 집합 크기 출력
        for(int i : answer){
            System.out.println(i);
        }
    }

    private static void dfs(int idx, int start, List<Integer> list){
        // 시작 지점을 담은 start값과, 탐색을 할 인덱스, 최종적으로 답에 추가 될 리스트
        if(!visited[idx]){ // 방문한 적이 없다면
            list.add(origin[idx]); // 리스트에 값 추가
            visited[idx] = true; // 방문 처리
            if(start == in[idx]){ // 만약 시작지점의 값과 들어온 값이 같다면
                answer.addAll(list); // 리스트에 있던 값을 전부 추가
                return;
            }
            dfs(in[idx] -1, start, list);
            visited[idx] = false; // 백트래킹을 위한 초기화
            /* 백트래킹을 해야하는 이유는
            만약 4 2 3 2 3 이라는 값이 들어오면 1번 인덱스에서 2번이 트루 처리가 됨
            이 때 2로 가서 3이 되면 이건 시작지점과 다르므로 리스트에 추가되지 못하고 마무리됨.
            다만, 2번 인덱스가 시작인 경우 2 -> 3 으로 가며 정확하게 리스트에 추가될 수 있음
            하지만 이미 visited가 트루가 되어있으므로 처리를 아예 하지 않음
            따라서 하나에 대한 꼬리를 물고 나서 다시 초기화를 해주어야 한다.
             */
        }

    }



}

간단한 아이디어만 있다면 문제 해결 자체에는 어려운 부분이 없을 것 같다.

다만, 다양한 예제를 떠올리며 반례를 생각할 수 있어야 할 것 같다.

따라서, 기본 예제만 맞췄다고 제출해보는 것이 아닌 항상 추가적인 예제(극단적인 케이스 1, 문제와는 다른 경우지만 흔한 케이스 1)을를 떠올려 보는 연습을 꼭 해야될 것 같다.