<코테 챌린지> 순열 사이클 (백준 10451번)

❓ 문제

📥 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

📤 출력

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

📥 예제 입력

2
8
3 2 7 8 1 4 5 6
10
2 1 3 4 5 6 7 9 10 8

📤 예제 출력

3
7

👩🏻‍💻 내 코드

import java.util.Scanner;

public class 순열사이클{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int T = in.nextInt(); 
        while (T-- > 0) {
            int N = in.nextInt();
            int[] permutation = new int[N + 1]; // 순열을 저장할 배열 (1부터 시작하므로 N+1)
            boolean[] visited = new boolean[N + 1]; // 방문 여부
            
            for (int i = 1; i <= N; i++) {
                permutation[i] = in.nextInt(); 
            }
            
            int cycleCount = 0;
            
            for (int i = 1; i <= N; i++) {
                if (!visited[i]) { 
                    dfs(permutation, visited, i);
                    cycleCount++; // 하나의 사이클을 찾았으므로 사이클 수 증가
                }
            }
                   
            System.out.println(cycleCount);
        }
        
        in.close();
    }
    

    private static void dfs(int[] permutation, boolean[] visited, int current) {
        visited[current] = true; 
        int next = permutation[current]; 
        
        if (!visited[next]) { // 다음 노드를 아직 방문하지 않았다면 DFS로 탐색
            dfs(permutation, visited, next);
        }
    }
}

 

💡 코드 접근

1. 방문 여부 체크: 각 숫자가 하나의 노드로 간주되므로, 해당 노드를 방문했는지 여부를 확인하기 위한 배열 visited를 사용한다.
2. DFS(깊이 우선 탐색): 사이클을 탐색하기 위해 DFS를 사용한다. 아직 방문하지 않은 숫자에서 시작하여 그 숫자가 가리키는 숫자를 재귀적으로 따라가면서 연결된 노드들을 모두 방문 처리한다.
3. 사이클의 개수 증가: DFS를 한 번 수행할 때마다 하나의 사이클을 발견한 것이므로 사이클의 개수를 증가시킨다.