[Algorithm] [Python] 백준/BOJ - 10451 _ 순열 사이클

10451 - 순열 사이클

 

문제

---

입력

---

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

출력

---

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

 

제출코드

---

import sys
sys.setrecursionlimit(10000)

def dfs(start):
    visited[start] = True
    next_path = path[start]
    if not visited[next_path]:
        dfs(next_path)


for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    path = [0] + list(map(int, sys.stdin.readline().split()))
    visited = [True] + [False] * n
    ans = 0

    for i in range(1, n+1):
        if not visited[i]:
            dfs(i)
            ans += 1
    print(ans)

 

문제 풀이

---

문제 핵심은 DFS 이다.

DFS를 통해 그래프를 순회하며 DFS가 실행될 때 마다 cnt값을 올려주면 싸이클의 개수를 확인할 수 있다.

DFS를 순회할 때 마다 연결된 노드들은 모두 순회할 것이기 때문에 DFS 한번에 사이클 한번을 순회할 수 있다.

값을 입력받고 순열을 모델링하여 그래프화 한다, 방문 여부를 저장하기 위한 변수 visited 도 정의한다.

이후 모든 노드에 방문여부를 순회하는 루프를 통해 순차적으로 접근하며 만일 i번째 노드를 방문하지 않았을 경우, 해당 노드를 시작점으로 하는 DFS를 실행한다.

cf) recursion limit 제한을 풀지 않으면 런타임 에러가 발생한다.