백준 : 10451 순열 사이클 [파이썬, 실버3]

문제

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

순열을 배열을 이용해 (1…i…nπ1…πi…πn)\(\begin{pmatrix} 1 & \dots & i & \dots &n \\  \pi_1& \dots& \pi_i & \dots & \pi_n \end{pmatrix}\) 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

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

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

입력

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

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

3
7

[문제 풀이]

1부터 N까지 정수로 만들 수 있는 순열의 한 가지 경우가 주어지 경우에 1부터 N까지 오름차 순으로 정렬한 순열과 1:1 대응해 만들 수 있는 그래프에서 순환 구조가 몇개 생기는 지 리턴하는 문제이다. 아래 그림과 같다. 윗줄이 from 두번째 줄이 to가 되는 그래프라고 생각하면 된다.

그려지면 다음과 같다.

DFS를 사용해 재귀 함수로 풀었다. 

 

[정답 코드]

import sys
sys.setrecursionlimit(10**7)

T=int(input())

def dfs(V):
    visited[V]=1  #방문한 곳 1로 표시
    next=arr[V]
    if visited[next]==0: #아직 방문하지 않은 곳인 경우
        dfs(next)

for i in range(T):
    answer = 0
    N = int(input())
    arr = [0] + list(map(int, input().split()))
    visited = [0] * (N + 1)

    for i in range(1, N+1):
        if visited[i]==0:
            dfs(i)
            answer+=1
    print(answer) #순열 사이클의 개수