[BEAKJOON] 백준 10451번 : 순열 사이클 - 파이썬

https://www.acmicpc.net/problem/10451

10451번: 순열 사이클

문제

입력

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

 

출력

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

 

---

접근

그래프 내에 순환하는 그래프를 어떻게 찾아야할지 고민이 필요했다.

다른 사람의 풀이를 참고하여 현재 방문한 노드의 다음 노드도 방문 표시가 되어있을 때, 순환하는 그래프라고 할 수 있다고 했다. 이를 활용하여 순환 그래프를 찾아낼 수 있다.

 

입력 : 테스트 개수 num // 순열의 크기 leng // 순열을 저장하는 리스트 input_list

각 노드가 노드를 따라 방문하고, 순환일 수 있기에 방문 체크 => visited

함수 정의

- 매개변수로 들어온 노드 v는 방문한거로 체크

- 갈 노드를 v로 가져옴

- 다음 노드인 next로 갈 수 있는 여부를 체크하고, 가능하면 재귀

 

코드

import sys

num = int(input())

def d(v):
    visited[v] = 1
    next = input_list[v]
    if(visited[next-1] == 0):
        d(next-1)
    return

while(num != 0):
    num -= 1
    leng = int(input())
    input_list = list(map(int, sys.stdin.readline().split()))

    visited = [0]*leng

    count = 0
    for i in range(leng):
        if(visited[i]==0):
            d(i)
            count += 1
    print(count)