[백준] 10451번 : 순열 사이클 Silver 3(실버 3) - JAVA[자바]

[Silver III] 순열 사이클 - 10451

문제 링크

성능 요약

메모리: 310056 KB, 시간: 1696 ms

분류

그래프 이론, 순열 사이클 분할

제출 일자

2023년 12월 10일 15:30:38

문제 설명

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 (1234567832781456)\(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3& 2&7&8&1&4&5&6 \end{pmatrix}\) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해 (1…i…nπ1…πi…πn)\(\begin{pmatrix} 1 & \dots & i & \dots &n \\ \pi_1& \dots& \pi_i & \dots & \pi_n \end{pmatrix}\) 로 나타냈다면, i에서 π_i로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

 

 

풀이 방법

1. dfs를 통해 한번 방문한 사이클은 방문하지 않도록 함

2. 스택(or 재귀)를 이용해서 구현

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

class Main {
    static int[] arr;
    static boolean[] visit;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int t = sc.nextInt();

        while (t-- > 0) {
            int result = 0;
            int n = sc.nextInt();
            arr = new int[n + 1];
            visit = new boolean[n + 1];
            for (int i = 1; i <= n; i++) {
                arr[i] = sc.nextInt();
            }
            for (int i = 1; i <= n; i++) {
                if (!visit[i]) {
                    result++;
                    checkGraph(i);
                }
            }
            sb.append(result).append("\n");
        }
        System.out.println(sb.toString());
    }

    private static void checkGraph(int start) {
        Stack<Integer> stack = new Stack<>();
        stack.push(arr[start]);
        while (!stack.isEmpty()) {
            int tmp = stack.pop();
            if (!visit[tmp]) {
                visit[tmp] = true;
                stack.push(arr[tmp]);
            }
        }
    }
}