[백준 10451] 순열 사이클

문제

 

입력

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

 

출력

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

---

접근

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

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

 

구현

- 아래는 재귀호출로 DFS를 구현한 것이다.

- 현재 방문한 노드를 방문 표시한다.

- 현재 방문한 노드의 다음 노드를 next_node에 저장하고

- next_node를 방문하지 않았다면 (즉 현재 노드를 기준으로 다음 노드) 재귀호출로 방문한다.

- 하지만 방문했다면 재귀가 멈추고 순환하는 그래프라는 것을 알 수 있다.

def DFS(node):
    visited[node] = True
    next_node = tree[node]
    if not visited[next_node]:
        DFS(next_node)

---

전체 코드

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

test_case = int(input())

def DFS(node):
    visited[node] = True
    next_node = tree[node]
    if not visited[next_node]:
        DFS(next_node)
for _ in range(test_case):
    N = int(input())
    tree = [0] + list(map(int, input().split()))
    visited = [False] * (N+1)
    answer = 0
    for i in range(1, N+1):
        if not visited[i]:
            DFS(i)
            answer += 1
    print(answer)