[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 2487번 _ 섞기 수열

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

2487번: 섞기 수열

[문제]

A1, A2, …, AN으로 표시된 N 개의 카드를 정해진 방법으로 섞고자 한다. 그 섞는 방법은 1에서 N까지의 숫자로 이루어진 수열로 표시된다. 이 수열을 섞기 수열이라 하자. 섞기는 현재 가지고 있는 카드에서 섞기 수열의 각 숫자가 나타내는 위치에 있는 카드를 순서대로 뽑아서 나열하는 것이다. 예를 들어, N = 6이고 섞기 수열이 [3, 2, 5, 6, 1, 4]라고 하자. 카드의 처음 상태가 [A1, A2, A3, A4, A5, A6]일 때, 섞기를 한 번 실행하면 카드의 순서가 다음과 같이 된다.

[A3, A2, A5, A6, A1, A4]

이 상태에서 다시 한 번 섞기를 실행하면 카드의 순서가 [A5, A2, A1, A4, A3, A6]이 되고, 다시 한 번 더 섞기를 실행하면 카드의 순서가 [A1, A2, A3, A6, A5, A4]가 된다. 이렇게 섞기를 반복하면 카드의 순서가 처음 상태인 [A1, A2, A3, A4, A5, A6]이 된다. 처음 상태로 돌아 올 때까지 반복한 섞기의 최소 횟수를 주어진 섞기 수열의 궤적이라 한다. 임의의 섞기 수열이 주어졌을 때, 그 섞기 수열의 궤적을 구하는 프로그램을 작성하시오.

 

[입력]

첫 번째 줄에 카드의 수 N이 주어진다. N은 1 이상 20,000 이하의 수이다. 두 번째 줄에 섞기 수열을 나타내는 N 개의 자연수가 빈칸을 사이에 두고 주어진다.

[출력]

첫 번째 줄에 입력으로 주어진 섞기 수열의 궤적을 출력한다. 단, 궤적이 1 이상 2,000,000,000 이하인 입력만 주어진다.

 

[아이디어]

1) 각 원소별 순환 사이클을 파악해 모은다.

2) 1)에서 모은 사이클의 최소 공배수를 출력한다.(파이썬 3.9버전부터는 math.lcm이 구현돼 있다.)

3) 각 사이클을 도는 동안 지나는 위치를 방문 표시함으로써 불필요한 중복 탐색을 막는다.

 

import math
import sys
sys.setrecursionlimit(10**5)
n=int(input())
m=[None]+list(map(int,input().split()))
v=[0]*(n+1)
ans = []
def cycle(x,c):
    global i
    v[x]=1
    if m[x]==i:
        return c
    elif not v[m[x]]:
        return cycle(m[x],c+1)
for i in range(1,n+1):
    if not v[i]:
        ans.append(cycle(i,1))
print(math.lcm(*ans))