[DFS,BFS] 백준 10451번 순열 사이클 java

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

10451번: 순열 사이클

순열을 배열을 이용하여 표현한후 이때 윗줄의 노드가 아랫줄의 노드방향으로 간선이 그려져서 만들어지는 사이클 개수를 구하는 문제이다.

 

 

예를 들어서 순열을 위와 같은 배열로 표현하면 1에서 3으로 향하는 간선 2에서 2로 향하는 간선 3에서 7로 향하는 간선등이 그려져서

위와 같은 그래프로 그려질 것이다.

 

소스코드

import java.util.*;

public class Main {
    static boolean[][] checked; //탐색여부
    static int[] N;
    static int T;
    static int[] cnt;
     static int[][] arr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        N = new int[T];
        cnt = new int[T];
        for(int i=0; i<T; i++){ //입력
            N[i] = sc.nextInt();
            arr = new int [T][];
            arr[i] = new int[N[i]+1];
            checked = new boolean[T][];
            checked[i] = new boolean[N[i]+1];

            for(int j=1; j<=N[i]; j++){
                arr[i][j] = sc.nextInt();
            }

            for(int j=1; j<=N[i]; j++){ //만약 해당 노드가 탐색이 안된 노드라면 dfs로 사이클 찾고 사이클 개수 늘리기
                if (checked[i][j]==false){
                    dfs(i, j);
                    cnt[i]++;
                }
            }
        }
        for(int i=0; i<T; i++){
            System.out.println(cnt[i]);
        }
    }


    public static void dfs(int i, int v) {
        checked[i][v] = true;
        if(checked[i][arr[i][v]]==false) {
            dfs(i, arr[i][v]);
        }
        return;
    }
}