[알고리즘/백준] 10451번 : 순열 사이클(Java)

문제	10451번 : 순열 사이클
문제링크	https://www.acmicpc.net/problem/10451
난이도	S3
언어	Java
분류	그래프이론 | 그래프이론, 그래프탐색, 순열 사이클 분할

 

 

📌 최종 정답 코드

import java.io.*;
import java.util.*;

public class Main {
    // 방문 여부를 저장할 배열 (각 인덱스의 노드가 방문되었는지)
    static boolean[] visited;

    // 입력으로 주어지는 순열을 저장할 배열
    static int[] permutation;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 테스트 케이스 수 입력
        int T = Integer.parseInt(br.readLine());

        // 각 테스트 케이스마다 처리
        while (T-- > 0) {
            // 순열의 길이 N 입력
            int N = Integer.parseInt(br.readLine());

            // 순열 배열 및 방문 배열 초기화
            permutation = new int[N + 1]; // 1-based index 사용
            visited = new boolean[N + 1];

            // 순열 정보 입력
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                permutation[i] = Integer.parseInt(st.nextToken());
            }

            int cycleCount = 0; // 사이클 개수를 셀 변수

            // 1부터 N까지의 모든 노드를 확인
            for (int i = 1; i <= N; i++) {
                // 아직 방문하지 않은 노드라면 새로운 사이클의 시작점
                if (!visited[i]) {
                    dfs(i); // 해당 노드를 시작으로 DFS 탐색
                    cycleCount++; // 탐색이 끝나면 하나의 사이클이 끝났음을 의미
                }
            }

            // 현재 테스트 케이스의 결과 출력
            bw.write(cycleCount + "\n");
        }

        // 출력 버퍼 비우고 닫기
        bw.flush();
        bw.close();
        br.close();
    }

    // DFS(깊이 우선 탐색)를 사용하여 사이클 탐색
    static void dfs(int node) {
        visited[node] = true; // 현재 노드 방문 처리

        // 순열에 의해 이동할 다음 노드
        int next = permutation[node];

        // 다음 노드를 아직 방문하지 않았다면 계속 탐색
        if (!visited[next]) {
            dfs(next);
        }

        // 이미 방문한 노드라면 사이클이 완성되었음을 의미하므로 종료
    }
}

📌 구해야 하는 정답

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

📌 코드 설계하기

1. 테스트 케이스 수 입력

2. 테스트 케이스마다 처리

 - 순열의 길이 입력

 - 순열 배열 및 방문 배열 초기화

 - 순열 정보 입력

 - DFS 탐색