[BFS / DFS] [백준 / 10451 ] 실버3 - 순열 사이클 (java/자바)

문제

성공 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static boolean[] isVisited;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(r.readLine());
        while (testCase-->0){
            int N = Integer.parseInt(r.readLine());
            arr = new int[N+1];
            isVisited = new boolean[N+1];
            StringTokenizer st = new StringTokenizer(r.readLine());
            for(int i=1; i<N+1;i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }

            int countLoop=0;
            for(int i=1;i<N+1;i++){
                if(!isVisited[i]) {
                    dfs(i);
                    countLoop++;
                }
            }
            System.out.println(countLoop);

        }
    }
    
    static void dfs(int index){
        isVisited[index] = true;

        int nextIndex = arr[index];
        if(!isVisited[nextIndex]){
            dfs(nextIndex);
        }

    }
}

왜 DFS로 풀었나요?

순열 사이클의 개수를 구하는 문제는 BFS(너비 우선 탐색)나 DFS(깊이 우선 탐색) 알고리즘 둘 다 사용할 수 있습니다.

BFS를 사용할 수도 있지만:

그러나 이 경우 DFS가 더 직관적이고 효율적인 선택입니다.
순열 사이클을 찾는 과정은 주어진 순열의 각 요소에서 시작하여, 해당 요소가 가리키는 다음 요소를 따라가며 사이클을 완성하는 과정입니다. 이 과정은 "깊이"를 따라 탐색하는 것과 유사하기 때문에 DFS가 더 적합합니다.