[백준] 순열 사이클

문제 설명

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

예제 입력/출력

제약 조건

문제 풀이

1️⃣ 순열 사이클 이란?

• 순열 사이클은 각 인덱스와 그 인덱스가 가리키는 값을 연결했을 때 형성되는 닫힌 경로를 의미한다.

• 순열을 하나의 방향 그래프로 생각한다.

• 각 숫자 가 가리키는 값을 라고 할 때, 로 가는 간선이 있다고 가정해보자.

• 예를 들어, 3 2 7 8 1 4 5 6 이라는 순열이 있다면
• 1번 요소가 3을 가리킴 (1 → 3)
• 3번 요소가 7을 가리킴 (3 → 7)
• 7번 요소가 5를 가리킴 (7 → 5)
• 5번 요소가 1을 가리킴 (5 → 1) → 하나의 사이클 완성: (1 3 7 5)

• 이런 식으로 모든 숫자는 반드시 하나의 사이클에 포함되게 된다.

2️⃣ 왜 모든 숫자는 반드시 하나의 사이클에 포함되지?

• 순열(Permutation)의 정의: 1부터 N까지의 숫자가 중복 없이 일대일로 대응되는 상태
• 나가는 선이 1개: 각 숫자(노드)는 반드시 다른 숫자 하나를 가리킨다. (나가는 방향의 간선이 무조건 1개)
• 들어오는 선이 1개: 각 숫자는 반드시 다른 숫자로부터 지목을 받는다. (들어오는 방향의 간선도 무조건 1개)

• 왜 막다른 길이 없을까?
• 만약 사이클이 생기지 않으려면 어디선가 길이 끊겨야 하는데 이 그래프에서는
• 어떤 숫자에서 출발해도 다음 숫자가 반드시 존재한다 (막다른 길 없음)
• 그런데 숫자의 개수는 N개로 한정적이다
• 계속 이동하다보면 결국 이전에 방문했던 숫자로 다시 돌아올 수 밖에 없다.

• 왜 ‘가지’가 생기지 않을까?
• 두 갈래 길이 합쳐지거나 갈라지는 경우는 없다.
• 합쳐지는 경우 (2 → 1, 3 → 1): 이러면 숫자 1을 두 번 쓰게 되어 순열의 규칙(중복 불가)이 깨진다.
• 갈라지는 경우 (1 → 2, 1 → 3): 숫자 1이 두 개의 숫자를 가리키게 되어 함수가 성립하지 않는다.

3️⃣ 그래프 탐색 (DFS 또는 BFS)

• 이 문제는 모든 노드를 방문하면서 연결된 노드들을 따라가다가, 이미 방문한 노드를 만나면 하나의 사이클이 끝난 것으로 간주하는 방식으로 풀 수 있다.

풀이 코드

T = int(input())

def dfs(node):
    next_node = node
    while not visited[next_node]:
        visited[next_node] = True
        next_node = arr[next_node]

for _ in range(T):
    N = int(input())
    arr = [0] + list(map(int, input().split()))

    visited = [False] * (N + 1)
    count = 0

    for i in range(1, N + 1):
        if not visited[i]:
            dfs(i)
            count += 1

    print(count)