백준 순열 사이클 10451

2020-10-22

1. 백준 순열 사이클 10451 문제

1.1. 문제

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

순열을 배열을 이용해 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

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

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

1.2. 입력

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

1.3. 출력

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

1.4. 예제 입력 1

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

1.5. 예제 출력 1

3
7

2. 컴퓨팅적 사고

해당 문제는 그래프문제입니다. 그래프문제로 해당 순열으로 주어졌을때 순열 사이클의 개수를 구해주면 됩니다.

문제에서 나와있듯이 (3, 2, 7, 8, 1, 4, 5, 6)의 배열을 이용하여 입력된 값들과 방향그래프로 만들어 낼 수 있습니다. 문제의 뜻을 이해하셨나요?

네 만약 8개의 수로 이루어져있을 경우 (1,2,3,4,5,6,7,8) 정점(Vertex)을 가지게 됩니다. 순서대로 들어온 입력 값들을 해당 정점들과 연결해주면 순열 그래프가 나온다는 말입니다.

순열과 그래프를 연결하기

1번 Vertex - Value 3 2번 Vertex - Value 2 3번 Vertex - Value 7 4번 Vertex - Value 8 5번 Vertex - Value 1 6번 Vertex - Value 4 7번 Vertex - Value 5 8번 Vertex - Value 6

하나의 그래프 형태에서 순열사이클의 개수를 구하는것이 포인트입니다. 즉 ,연결요소를 이루는 집합이 몇개인지를 찾으면 됩니다. 따라서, 하나의 정점들과 연결된 그래프들은 모두 Check를 시키게 될 것이고, 이때 DFS를 이용하여 인접 리스트로 값을 처리하였고 한번 순회시 Cnt+1값을 처리하여 순열 사이클의 개수를 구할 수 있도록 하였습니다.

3. 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 순열사이클10451 {
    static int t;
    static int n;
    static boolean[] check;
    static ArrayList<ArrayList<Integer>> A;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());

        while(t-- > 0){
            n = Integer.parseInt(br.readLine());
            check = new boolean[n+1];
            StringTokenizer st;
            A = new ArrayList<>();
            for(int i=0; i<=n; i++){
                A.add(new ArrayList<>());
            }
            st = new StringTokenizer(br.readLine(), " ");
            for(int i=0; i<n; i++){

                int x = i+1;
                int y = Integer.parseInt(st.nextToken());
                A.get(x).add(y);
                A.get(y).add(x);
            }
            int cnt = 0;
            for(int i=1; i<=n; i++){
                if(!check[i]){
                    dfs(i);
                    cnt++;
                }
            }
            System.out.println(cnt);
            Arrays.fill(check,false);
        }
    }

    private static void dfs(int x) {
        check[x] = true;
        for(int i=0; i<A.get(x).size(); i++){
            int y = A.get(x).get(i);
            if(!check[y]){
                dfs(y);
            }
        }
    }
}

AlgorithmBOJ