[백준]10451번, 순열 사이클

백준 Q.10451 순열 사이클

문제:

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

 

 

와 같다. 또는 Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해

 

로 나타냈다면, i에서 ∏i 로 간선을 이어 그래프를 만들 수 있다. Figure1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8 1, 4, 5, 6)에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

 

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

 

입력 :

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

 

출력 :

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

 

<소스 코드>

import java.util.*;
 
public class Main {
    static boolean[] address; // 정점 위치
    static int[] n; //정점 내용물
    static int answer = 0; //정답 카운트
 
    static void search(int addressIndex){
 
        if(address[addressIndex]){//이미 방문했던 곳이라면(true) 순열이므로 count + 1, 나오기
            answer++; return;}
 
        int nextAddress;
 
        address[addressIndex] = true; // i 위치 true로 방문표시
        nextAddress = n[addressIndex] - 1;// 그 다음으로 방문할 정점 위치 저장
 
        search(nextAddress);// 다음 정점으로
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int T = sc.nextInt();
 
        for (int test_case = 0; test_case < T; test_case++) {
            int size = sc.nextInt();
 
            address = new boolean[size];//정점(순열) 위치 ex) 1,2,3,4,....8
            n = new int[size];//순열(정점 내용물) ex) 3,2,7 .... 6
            answer = 0;
 
            for (int i = 0; i < size; i++)//순열 입력
                n[i] = sc.nextInt();
 
            for (int i = 0; i < size; i++) {
                if (!address[i]) {//i 정점에 방문하지 않았다면
                    search(i);
                }
            }
            System.out.println(answer);
        }
    }
}
 
 

 

<실행 결과>

 

<해법>

*정점(address)의 내용물(n)이 다음에 방문할 정점(nextAddress)이다.

 재귀호출을 이용한다. (DFS)

1. 정점에 방문할 때 마다 true로 방문 표시를 해준다.

2. 다음 정점(nextAddress)으로 이동, 다음 정점이 true면 count + 1 하고 빠져나오고 false면 계속 진행한다.

 

 

문제 사이트 및 참고 사이트 : https://www.acmicpc.net/problem/10451

※
본 게시물은 개인적인 용도로 작성된 게시물입니다. 이후 포트폴리오로 사용될 정리 자료이니 불펌과 무단도용은 하지 말아주시고 개인 공부 목적으로만 이용해주시기 바랍니다.

※