[백준] 10451번: 순열 사이클 (Java)

문제: https://www.acmicpc.net/problem/1012번

📌 문제 탐색하기

입력 : 첫째 줄 - 테스트 케이스 개수 T
각 테스트 케이스에 대한 첫번째 줄 - 순열의 크기 N (2 ≤ N ≤ 1,000)
각 테스트 케이스에 대한 두번째 줄 - 순열
출력 : 각 테스트 케이스마다 입력으로 주어진 순열에 존재하는 순열 사이클의 개수

가능한 시간복잡도

O(V + E)
V : 정점의 수
E : 간선의 수

알고리즘 선택

DFS

📌 코드 설계하기

1. 테스트 케이스의 수 T를 입력받고, 각 T마다 순열의 크기와 순열을 입력받는다.
2. visited를 이용해 이미 방문한 노드를 표시한다.
3. 각 요소에 대해 방문하지 않았다면 dfs 함수를 호출해 사이클을 찾는다.
4. DFS를 이용해 주어진 시작점에서 다음 노드로 이동하고, 이미 방문한 노드를 만날 때까지 반복하여 사이클을 완성한다.
5. 각 사이클을 찾을 때마다 cycleCount를 증가시킨다.
6. 모든 사이클을 찾은 후에 그 수를 출력한다.

📌 시도 회차 수정 사항 (Optional)

💡 시도별 수정 사항은 어떻게 작성하나요?
- 무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면 , 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 됩니다.
- 틀렸습니다를 받았다면 왜 틀렸는지 고민해보고 , 어떻게 수정할 수 있는지 고민하는 과정을 작성해주시면 됩니다.
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검해보세요
- 한번에 맞출수도 있기 때문에 이 칸은 Optional입니다.

1회차

2회차

📌 정답 코드

import java.util.*;

public class Main {
    private static int[] arr;
    private static boolean[] visited;
    private static int n;

    private static void dfs(int start) {
        if (visited[start]) return;
        visited[start] = true;
        dfs(arr[start]);  // 다음 연결된 노드로 이동
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // 테스트 케이스의 수

        while (T-- > 0) {
            n = scanner.nextInt(); // 순열의 크기
            arr = new int[n + 1];
            visited = new boolean[n + 1];

            for (int i = 1; i <= n; i++) {
                arr[i] = scanner.nextInt(); // 순열 입력
            }

            int cycleCount = 0;
            for (int i = 1; i <= n; i++) {
                if (!visited[i]) {
                    dfs(i);
                    cycleCount++;  // 새로운 사이클 발견
                }
            }
            System.out.println(cycleCount);
        }
        scanner.close();
    }
}