PS/백준

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

제이온 (Jayon) 2020. 6. 5.

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

 

10451번: 순열 사이클

문제 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8

www.acmicpc.net

문제

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

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

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

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

 

풀이

여러 가지 방법이 있지만, 저는 인접리스트와 DFS를 이용하여 풀었습니다. 문제의 예제에서 나와있듯이 1과 3, 2와 2, 3과 7을 각각 인접리스트로 구현해 주었습니다. 그리고 DFS를 통해서 인접리스트와 연결된 요소를 전부 visited[i] = true로 처리를 시켜줍니다. 메인 함수에서는 반복문으로 DFS를 여러 번 돌리게 되는데, 이 때 아직 방문하지 않은 점만 DFS를 실행하도록 만들면 순열 사이클의 개수를 구할 수 있습니다.

아래는 위 풀이를 기반으로 작성한 소스코드입니다.

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            ArrayList<ArrayList<Integer>> a = new ArrayList<>(); // 연결 리스트
            for (int i = 0; i <= N; i++) {
                a.add(new ArrayList<>());
            }
 
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                int t = Integer.parseInt(st.nextToken());
                a.get(i).add(t);
            }
 
            boolean[] visited = new boolean[N + 1];
            int cnt = 0;
            for (int i = 1; i <= N; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    DFS(a, visited, i);
                    cnt++;
                }
            }
            bw.write(cnt + "\n");
        }
 
        bw.flush();
        bw.close();
        br.close();
    }
 
    // DFS를 통해서 start와 연결된 점을 visited[i] = true로 처리함.
    public static void DFS(ArrayList<ArrayList<Integer>> a, boolean[] visited, int start) {
 
        for (int i : a.get(start)) {
            if (!visited[i]) {
                visited[i] = true;
                DFS(a, visited, i);
            }
        }
    }
 
}
cs

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.

댓글

추천 글