Skip to main content
동호의 블로그

[백준] 순열 사이클

•2 min•311 words

https://www.acmicpc.net/problem/10451

문제 설명

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

예제 입력/출력

  • 예제 입력 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

제약 조건

  • $2 ≤ N ≤ 1,000$

문제 풀이

1️⃣ 순열 사이클 이란?

image.png

  • 순열 사이클은 각 인덱스와 그 인덱스가 가리키는 값을 연결했을 때 형성되는 닫힌 경로를 의미한다.
  • 순열을 하나의 방향 그래프로 생각한다.
  • 각 숫자 ii가 가리키는 값을 P[i]P[i]라고 할 때, i→P[i]i \to P[i] 로 가는 간선이 있다고 가정해보자.
  • 예를 들어, 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)