백준 2668번: 숫자고르기[JAVA]

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

2668번: 숫자고르기

 

[정답 코드]

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

public class Main {
    static int n, num;
    static int[] arr;
    static boolean[] check;
    static List<Integer> answer;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        check = new boolean[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine()) - 1;
        }
        answer = new LinkedList<>(); // 답은 가변적이므로 리스트로 선언

        for (int i = 0; i < N; i++) {
            check[i] = true;
            num = i;
            dfs(i);
            check[i] = false;
        }
        Collections.sort(answer);
        System.out.println(answer.size());
        for (Integer integer : answer) {
            System.out.println(integer + 1);
        }
    }

    public static void dfs(int i) {
        if (arr[i] == num) { // 한바퀴돌아 다시 제자리로 돌아오는지 체크
            answer.add(num); // 돌아온다면 정답에 추가
        }
        if (!check[arr[i]]) {
            check[arr[i]] = true;
            dfs(arr[i]);
            check[arr[i]] = false;
        }
    }
}

 

[설명]

난이도가 높아질수록 문제를 이해하는것 자체부터가 힘들어진다. for문을 N번 만큼 돌면서 dfs 로직을 실행시켜준다.

dfs로직은 출발 숫자 -> arr[출발 숫자] -> arr[arr[출발 숫자]] 를 반복하다 출발 숫자를 다시 만나게 되면 첫째 줄과 둘째 줄 정수들의 집합이 일치한다고 볼 수 있다. 

for문을 N번 만큼 실행시키는 이유는 최대값을 찾기 위해서이다.