백준 10451 순열 사이클 자바

문제 링크

문제 풀이

처음 푸는 간선 그래프 탐색 문제다. 처음 풀었지만 기존 dfs나 bfs와 인접 매트릭스를 그릴때 방향 체크하는 방법만 빼면 큰 차이가 없었다. 독립된 순열의 싸이클을 구하기 위해서 dfs() 함수를 호출할 때 count를 세주고 이를 출력하여 답을 구했다.

코드

import java.util.*;
public class Main {

    static boolean[][] map;
    static boolean[] visit;


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int i=0; i<t;i++){
            int count=0;
            int n = sc.nextInt();
            map = new boolean[n+1][n+1];
            visit = new boolean[n+1];
            for(int x=1;x<=n;x++){
                int to = sc.nextInt();
                map[x][to]=true;
            }
            for(int x=1;x<=n;x++){
                if(!visit[x]){
                    count++;
                    dfs(x, n);
                }
            }
            System.out.println(count);
        }

        
        
    }
    static void dfs(int i, int n){
        Queue<Integer> q = new LinkedList<>();
        q.offer(i);
        visit[i]=true;
        while(!q.isEmpty()){
            int tmp = q.poll();
            for(int j=1;j<=n;j++){
                if(map[tmp][j]&&!visit[j]){
                    visit[j]=true;
                    q.offer(j);
                }
            }
        }
    }
}