[백준 Silver 2] 10451 순열 사이클 - Java

문제링크 : https://www.acmicpc.net/problem/10451

10451번: 순열 사이클

 

접근 과정 : 

• 분리 집합이 바로 떠올랐기 때문에, 분리집합으로 접근했다.
• 순열의 크기만큼 집합 배열을 선언한다.
• 순열의 인덱스가 해당 원소를 가리키기 때문에, 인덱스와 원소를 합친다(union).
• 모든 순열의 순회한 뒤에, 집합 배열의 값이 0인 원소를 카운트 한다.

 

소스 코드 및 결과 :

package BOJ;

/* 
    순열 사이클
*/

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

public class BOJ10451 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder answer = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            cycle = new int[N + 1];

            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                int num = Integer.parseInt(st.nextToken());

                union(i, num);

            }

            int count = 0;
            for (int i = 1; i <= N; i++) {
                if (cycle[i] == 0) {
                    count++;
                }
            }

            answer.append(count).append("\n");
        }

        System.out.println(answer.toString().trim());
    }

    static int[] cycle;

    static int findRoot(int n) {
        if (cycle[n] == 0) {
            return n;
        }

        return cycle[n] = findRoot(cycle[n]);
    }

    static void union(int a, int b) {

        a = findRoot(a);
        b = findRoot(b);

        if (a != b) {
            cycle[b] = a;
        }
    }
}

 

P.S