백준 10451 순열 사이클 Python: 재귀 없이 O(N)으로 세기

백준 10451 순열 사이클은 방문하지 않은 수에서 탐색을 시작할 때마다 사이클 수를 1 늘리면 풀 수 있다. 입력이 일반 방향 그래프가 아니라 1부터 N까지의 순열이므로, 각 정점의 진입 차수와 진출 차수가 모두 1이고 모든 연결 성분은 정확히 하나의 사이클이다.

Python에서는 재귀 DFS보다 while 반복문이 안전하다. N이 1,000까지이고 하나의 사이클 길이도 1,000이 될 수 있어, 실행 환경의 재귀 한계에 가까워질 수 있기 때문이다.

순열을 방향 그래프로 바꿔 본다

순열 P에서 정점 i가 P[i]를 가리킨다고 생각한다.

P = [2, 3, 1, 5, 6, 4]

1 → 2 → 3 → 1
4 → 5 → 6 → 4

사이클은 (1, 2, 3), (4, 5, 6) 두 개다. 순열에서는 모든 값이 정확히 한 번 등장하므로, 탐색 중 다른 나뭇가지로 빠지거나 꼬리만 있는 연결 성분이 생기지 않는다.

이 성질 덕분에 아직 방문하지 않은 start를 발견했다는 사실만으로 새 사이클 하나를 찾았다고 판단할 수 있다.

반복문으로 사이클을 센다

def count_cycles(permutation: list[int]) -> int:
    visited = [False] * len(permutation)
    cycles = 0

    for start in range(1, len(permutation)):
        if visited[start]:
            continue

        cycles += 1
        current = start

        while not visited[current]:
            visited[current] = True
            current = permutation[current]

    return cycles

함수의 반환값은 “현재 재귀가 사이클을 찾았는가” 같은 신호가 아니라, 전체 순열에서 센 사이클 개수다. 새 미방문 정점에서 출발하면 cycles를 먼저 1 늘리고, 이미 방문한 정점으로 돌아올 때까지 현재 사이클의 정점을 표시한다.

일반적인 함수형 그래프라면 미방문 정점에서 시작한 경로가 기존 컴포넌트로 합류할 수도 있어 이 논리를 그대로 쓰면 안 된다. 이 문제에서 가능한 이유는 입력이 순열이라고 보장되기 때문이다.

전체 Python 코드

import sys

input = sys.stdin.readline


def count_cycles(permutation: list[int]) -> int:
    visited = [False] * len(permutation)
    cycles = 0

    for start in range(1, len(permutation)):
        if visited[start]:
            continue

        cycles += 1
        current = start

        while not visited[current]:
            visited[current] = True
            current = permutation[current]

    return cycles


test_cases = int(input())
answers = []

for _ in range(test_cases):
    n = int(input())
    permutation = [0] + list(map(int, input().split()))
    answers.append(str(count_cycles(permutation)))

print("\n".join(answers))

각 정점은 한 번만 방문하므로 테스트 케이스 하나의 시간 복잡도는 O(N), 방문 배열의 공간 복잡도는 O(N)이다. Python의 재귀 한계를 변경할 필요도 없다.

예제와 무작위 순열로 확인하기

문제 예제의 두 순열은 각각 3개와 7개의 사이클을 만든다.

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

출력
3
7

반복문 구현은 이 예제와 함께, 길이 2부터 99까지 만든 1,960개 무작위 순열을 독립적으로 분해한 결과와 비교해 모두 일치함을 확인했다.

그래프의 정점과 간선 표현이 먼저 필요하다면 그래프와 DFS·BFS 기초를, 일반적인 반복형 DFS의 방문 순서는 백준 24479·24480 DFS를 함께 볼 수 있다.

참고 자료

• 백준 10451 순열 사이클
• Python 문서: sys.getrecursionlimit()