[백준-10451] 순열 사이클- Python

 

 

문제 소개

 

문제

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

 

 

사용한 알고리즘

 

 

DFS

 

 

Code 

 

# Python code
import sys
import copy

sys.stdin = open("input.txt", "r")

###########################################################
import sys
import collections
import itertools
import copy
sys.setrecursionlimit(10**7)

input=sys.stdin.readline

N = int(input())


def DFS(startNode):
	# DFS로 탐색하면서 도착햇던 Node는 Check Array에 1로 표시
    
    global Ans

    # Arrival check
    if check[startNode]==1 :
        return
    else:
        check[startNode]=1

    # Search Next node
    # 특히 다음 Node를 탐색할때 Check Array에 이미 1이 있으면 Ans을 올리고 종료
    NextNode = Arr[startNode][1]
	
    if check[NextNode]==1:
        Ans += 1
    else:
        DFS(NextNode)


for _ in range(N):
    Ans = 0
    n = int(input())
    Arr = list(enumerate(list(map(lambda x : int(x)-1, input().split()))))
    check = [0]*n

    for ix in range(n):
        DFS(ix)

    print(Ans)

 

 

 

※ end