백준 10451번 순열 사이클

출처 : 10451번: 순열 사이클 (acmicpc.net)

10451번: 순열 사이클

---

순열 사이클 성공 출처 다국어 분류

한국어   

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

1 초

256 MB

11669

7401

5315

63.176%

문제

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개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

 

---

[ 문제 설명 ]

 

우선 순열의 개수를 구한다는 것이고, figure의 예시에서 자칫 규칙성이 존재해서 규칙이 있는 순열로 생각할 수 있으나, 그것이 아니라 말 그대로 수가 나열돼있는 순열의 개수를 세는 거라는 걸 명심하길 바란다.

 

이점을 명심했고,  제가 그래프이론 중 하나를 이용할 거라고 말하면 떠올르는 알고리즘이 없나요?

.

.

.

.

네 ㅂ ㅏ로! DFS입니다!! 왜일까요 그림으로 설명드립니다.

 

그림 1 - 순열 사이클 설명

 

---

코드를 보겠습니다

 

[ 코드 ]

 

def DFS(num):
    #print(num, end=' ')  # 처음 방문한 그 지점을 출력

    visited[num] = 1  # 방문했을 때 그 방문리스트에 0으로 되어있을 텐데, 그것을 1로 바꾸어준다.
    number = numbers[num]
    if not visited[number]:
            #print(number, end="#")
            DFS(number)

for _ in range(int(input())):
    N = int(input())
    numbers = [0] + list(map(int, input().split()))
    #print(numbers)
    visited = [1] + [0] * N  # 방문여부확인용
    result = 0

    for i in range(1, N + 1):
        if not visited[i]:
            DFS(i)
            result += 1  # 순열의 개수 세기!
    print("result", result)
    #print(result)

그림과 설명을 이해하신 다음 코드를 음미해보시면 이해가 되실 겁니다.

 

---

후기

 

순열을 나도 모르게 규칙 있는 순열이라고 착각해서 잠시 어렵게 생각한 문제 중 하나

사실은 매우 쉬운 건데.. ㅎㅎ