[백준] 10451 순열 사이클

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

10451번: 순열 사이클

 

사실 명칭을 DFS 메소드라고 붙였는데 엄밀히 따지면 DFS 라기보다는 조건에 맞는 인덱스를 찾아서 스택에 넣는 기능이다. 편의상 명칭을 이렇게 했고, 인덱스 자체가 0으로 시작하는 것을 유의한다면 무난하게 풀 수 있는 문제라고 생각한다.

---

문제 및 입출력 예제

 

---

코드

import java.util.Scanner;
import java.util.Arrays;
import java.util.Stack;

public class Main
{
    // 미니 dfs 실행
    public static void dfs(int[] arr, boolean[] visit, int start)
    {
        Stack<Integer> s = new Stack<Integer>();
        int cnt = 0;
        s.add(start);
        
        while(!s.isEmpty())
        {
            int index = s.pop();
            
            if(!visit[index])
            {
                visit[index] = true;
                s.add(arr[index]);
            }
        }
    }
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        
        for(int i=0; i<t; i++)
        {
            int n = sc.nextInt();
            int[] arr = new int[n];
            int cnt = 0;
            boolean[] visit = new boolean[n];
            
            for(int j=0; j<n; j++)
            {
                arr[j] = sc.nextInt()-1;
            }
            
            Arrays.fill(visit, false);
            
            for(int j=0; j<n; j++)
            {
                if(!visit[j])
                {
                    dfs(arr, visit, j);
                    cnt++; // dfs 실행만큼 +1
                    visit[j] = true;
                }
            }
            
            System.out.println(cnt);
        }
        
        sc.close();
    }
}