[백준] 10451번 순열 사이클 Python

📃문제

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면

와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해

로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

📃입력

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

📃출력

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

📃예제 입력 1

2
8
3 2 7 8 1 4 5 6
10
2 1 3 4 5 6 7 9 10 8

📃예제 출력 1

3
7

✏️문제 탐색하기

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 문제.

✏️알고리즘 선택

그래프 탐색인 DFS를 사용하여 방향 그래프에서 사이클을 개수 찾기.
각 테스트 케이스에서 DFS를 통해 모든 노드를 한 번만 방문하므로 O(N).

✏️코드 설계하기

1. T에 테스트 케이스의 개수를 입력받습니다.
2. 각 테스트 케이스에서 순열의 개수 N 과 순열을 입력받아 리스트에 저장합니다.
3. 스택을 사용해 DFS를 구현합니다.
4. 스택에서 노드를 꺼내 다음 노드로 이동하며 방문 여부를 확인합니다.
5. 탐색이 끝날 때마다 사이클이 하나 발견됩니다.
6. 방문하지 않은 노드에서 DFS를 시작할 때마다 사이클 개수를 증가시킵니다.
7. 각 테스트 케이스의 결과인 개수를 출력합니다.

✏️코드 구현

import sys


list_ = []

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


def dfs(v):
    n = len(v)
    visited = set()
    count = 0  # 사이클 개수 초기화

    for start in range(1, n + 1):
        if start not in visited:
            stack = [start]
            visited.add(start)
            while stack:
                node = stack.pop()
                next_node = v[node - 1]
                if next_node not in visited:
                    stack.append(next_node)
                    visited.add(next_node)
            count += 1
    return count


for _ in range(T):
    N = int(sys.stdin.readline())
    values = list(map(int, sys.stdin.readline().split()))
    list_.append(dfs(values))


for a in list_:
    print(a)