[백준 10451] 순열 사이클 (Sliver 2)

문제

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

접근

1. 주어진 입력값을 그래프로 만들어 준다.
2. dfs를 이용해 자식 노드가 조상 노드와 연결이 되있으면 cycle이 존재하는 성질을 이용한다.
3. dfs 함수 파라미터에서 start는 조상, curr은 현재 자식 노드

Code

import sys
from collections import defaultdict

t = int(sys.stdin.readline())


def dfs(start, curr):
    if start == curr and visited[curr]:
        global answer
        answer += 1
        return

    visited[curr] = True
    for next_node in graph[curr]:
        dfs(start, next_node)


for _ in range(t):
    n = int(sys.stdin.readline())
    answer = 0
    graph = defaultdict(list)
    visited = [False] * (n + 1)
    nums = list(map(int, sys.stdin.readline().split()))
    for idx, num in enumerate(nums):
        graph[idx + 1].append(num)
    for i in range(1, n + 1):
        if not visited[i]:
            dfs(i, i)
    print(answer)

여담

난이도가 실버 2이긴 하지만 사이클에 대한 개념잡기 좋은 문제.