[Python] 2487번 섞기 수열

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

2487번: 섞기 수열

---

 

24/03/21

 

 

순열 사이클 분할의 개념을 알고 있으면 쉽게 해결할 수 있는 문제이다.

---

 

문제 접근 방식:

 

 

모든 순열(Permutation)은 일정한 사이클들로 "분할"할 수 있다는 개념이 순열 사이클 분할이다.

 

순열 사이클 분할에 대해서 더 자세히 알고 싶다면 아래 링크를 참고해보자.

 

https://en.wikipedia.org/wiki/Permutation#Cycle_notation

Permutation - Wikipedia

 

아니면 John B. Fraleigh의 A First Course in Abstract Algebra (7th Ed.)의 Theorem 9.8을 보자.

 

우리의 목적은 하나의 순열 $P$가 몇 번 합성해야 항등 함수 $I$가 되는지를 찾아내야 한다.

 

이는 순열 $P$에 존재하는 모든 사이클들의 크기를 $c_1, c_2, \cdots, c_n$이라고 했을 때, $\mathrm{lcm} (c_1, c_2, \cdots, c_n)$이 된다.

 

그 이유는, 어떤 사이클의 크기가 $c_i$라고 한다면, 순열 $P$를 $a \cdot c_i$($a$는 정수)번 합성하면 그 사이클 내의 모든 원소가 다시 자기 자신으로 돌아오기 때문이다.

 

따라서, 모든 사이클의 원소들이 다시 자기 자신으로 돌아오기 위해서는 적어도 $\mathrm{lcm} (c_1, c_2, \cdots, c_n)$번이 필요하다.

 

어떤 사이클의 크기를 찾기 위해서는 DFS를 사용할 수 있다.

 

이때, 파이썬은 최대 재귀 깊이가 $1,000$으로 설정되어있기 때문에 sys.setrecursionlimit()으로 재귀 깊이를 충분히 늘려주어야 함에 유의하자.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2487번 섞기 수열
# DFS, 그래프 이론, 순열 사이클 분할
'''
접근 방법:
하나 잡고 DFS
모든 곳을 방문할 때까지 반복
이후 순열 사이클 크기의 lcm을 구한다.
'''
import sys
input = sys.stdin.readline
from math import lcm
sys.setrecursionlimit(100_000)

N = int(input())
A = list(map(lambda x: int(x)-1, input().rstrip().split()))
visited = [0 for _ in range(N)]
def dfs(i, cycle_length):
    if visited[i]:
        return cycle_length
    visited[i] = 1
    return dfs(A[i], cycle_length+1)
nums = []
for i in range(N):
    if visited[i] == 0:
        num = dfs(i, 0)
        nums.append(num)
print(lcm(*nums))