[백준] 10451번 순열 사이클

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

순열 사이클을 구하는 문제. DFS를 이용하여 몇 개의 연결요소(나누어진 각각의 그래프)가 나오는지 구하는 문제이다.

나의 풀이

1. dfs() 함수를 구현하여 방문한 노드를 표시하고 해당 노드에서 연결된 다음 노드 재귀를 돌려준다. 모든 정점에서 방문할 수 있는 노드는 1개이기 때문에 다음 노드만 연결해 주면 된다.

2. 1번 노드에서 N번 노드까지 모든 노드에 대해서 for문을 돌려준다. 방문하지 않았으면 dfs 함수를 호출한다.
   예를 들어 첫 번째 사이클은 1에서 시작하여 1 -> 3 -> 7 -> 5 로 사이클을 만든다. 이 때문에 3, 5, 7 번째에서는 dfs 호출을 하지 않는다.
   이렇게 dfs()를 호출하는 개수를 세면 count를 구할 수 있다.

이 문제도 역시 재귀의 제한을 풀어주어 런타임 에러를 방지해야 한다.

T : 테스트 케이스 횟수
N : 정점의 개수
inputNums : 입력된 순열

import sys
sys.setrecursionlimit(10000)
T = int(sys.stdin.readline())

def dfs(idx):
    if check[idx] != 0:
        return
    check[idx] = 1

    next_node = nodes[idx][0]
    if check[next_node] == 0:
        dfs(next_node)

for _ in range(T):
    N = int(sys.stdin.readline())

    inputNums = list(map(int, sys.stdin.readline().split()))

    nodes = [[] for _ in range(N+1)]
    check = [0]*(N+1)
   
    count = 0
    for i in range(N):
        nodes[i+1].append(inputNums[i])
   
    for index in range(1, N+1):
        if check[index] == 0:
            dfs(index)
            count += 1
    print(count)