[백준 22863] 원상 복구 (large) (python)

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

22863번: 원상 복구 (large)

원상 복구 (large) 문제

PDi 값을 i 번째로 가져오는 셔플을 K번 작업했을 경우, 최종적으로 출력되는 결과 카드를 구해보자.

순열 사이클을 찾아내서 계산해야 하는 문제

⚙️정답 코드

import sys
N, K = map(int, sys.stdin.readline().split())
P = [0] + list(map(int, input().split()))
S = [0] + list(map(int, input().split()))
D = [0]*(N+1)
result = [0]*(N+1)
visited = [False]*(N+1)
for i in range(1, N+1): 
    if visited[i]: # 찾아본거면
        continue 
    cnt, num = 0, i 
    while not visited[num]: # 방문 안했으면 // 순열 사이클 구해주는 과정
        visited[num] = True # 방문 처리하고
        D[cnt] = num # S에서 가져온 num을 D에서 추가해가기
        cnt += 1 # 인덱스 하나씩 늘려가자
        num = S[num] # S의 num 인덱스 값을 가져오기
    for j in range(cnt): # cnt = 해당 순열의 사이클 수
        x = P[D[j]] # 결과로 출력할 것의 값 = 카드 한번 바꿔 준 것 
        y = D[(j+K)%cnt] # 그때 인덱스 = j+K를 사이클로 나눠준 값
        result[y] = x # 위에 두개 반영
print(*result[1:])

📌문제 접근 포인트

1. 원상 복구과정에서 K가 무려 10^15로 굉장히 큰 숫자이다. 이걸 반복해서 해결 할 경우 3초안에 계산이 불가능하다.
2. 그렇다면 카드 셔플의 규칙성을 찾아보자. (예시)
1회 셔플 진행 → 3 5 1 4 2
2회 셔플 진행 → 1 4 5 3 2
3회 셔플 진행 → 5 3 4 1 2
4회 셔플 진행 → 4 1 3 5 2
5회 셔플 진행 → 3 5 1 4 2
...
1회와 5회가 동일한 것을 볼 수 있다.
3. 자세히 보면 셔플의 카드는 3, 5, 1, 4만 카드의 위치가 바뀌고 2번 카드는 바뀌지 않는 것을 볼 수 있다. 이렇게 순열의 반복을 이루는 것을 순열 사이클이라고 부른다.
4. 즉 이 사이클을 구해서 K를 나눠주면 10^15까지 해당하는 K를 굉장히 줄여줄 수 있다.
5. 우선 각 카드는 인덱스와 1차이나므로, 앞에 [0]을 더해줘서 카드숫자를 인덱스로 바꿀 수 있게 구성하고, 순열 사이클을 구하기 위해 방문 처리를 해줄 수 있게 visited를 구성해보자. 
6. 순열 사이클을 찾기 위해 while 문을 통해 하나씩 방문 처리 해주면서 S의 num인덱스에 해당하는 값을 D에 넣어주면 순열 사이클을 찾을 수 있다.
7. 찾은 순열 사이클의 갯수를 기반으로 결과 값과 인덱스 값을 찾아 result 값에 반영해주면 원하는 K번 돌렸을 때 횟수를 찾아 낼 수 있다.