[백준] 1091 - 카드 섞기

문제 링크

https://www.acmicpc.net/group/workbook/view/20862/74461

문제 요약

지민이는 N개의 카드를 섞어서 3명의 플레이어(0, 1, 2)에게 나누어주는 카지노 딜러입니다. 카드는 순서대로 플레이어 0, 1, 2에게 돌아가며 분배됩니다. 지민이는 카드를 섞어 특정 카드가 원하는 플레이어에게 가도록 해야 합니다. 카드를 섞을 때, 각 카드는 미리 정의된 순열 S에 따라 이동합니다. 목표는 최종적으로 각 카드가 배열 P에 정의된 대로 특정 플레이어에게 가는 상태를 만드는 것이며, 이를 위해 필요한 최소 섞는 횟수를 구하는 것입니다. 만약 목표 상태에 도달할 수 없다면 -1을 반환합니다.

푼 방법

 

• 카드 목표 위치 설정: 배열 P에 따라 각 카드가 가야 할 플레이어를 미리 저장했습니다.
• 상태 중복 검사: 카드의 현재 상태가 반복되면 더 이상 의미가 없으므로 set을 사용해 이미 나온 상태를 저장하고 중복을 확인했습니다.
• 이동 함수 (move): 현재 카드 위치를 순열 S에 따라 한 번 섞은 후 새로운 위치로 업데이트하는 함수를 작성했습니다.
• 목표 상태 확인 (chk): 현재 카드 위치가 원하는 플레이어에게 올바르게 분배되었는지 검사하는 함수를 작성했습니다.
• 반복: chk 함수가 원하는 상태를 만족할 때까지 카드를 섞고 섞은 횟수를 기록했습니다. 만약 중복된 상태가 발생하면 -1을 출력하여 종료했습니다.

 

정답 코드

import sys
n=int(input())
p = list(map(int, sys.stdin.readline().split()))
s = list(map(int, sys.stdin.readline().split()))

finalpos = [[] for _ in range(3)]
curr_pos = [p for p in range(n)]

for i in range(n):
    finalpos[p[i]].append(i)        

case = set()
case.add(tuple(curr_pos))

def move(curr_pos):
    next_pos = [None] * (n)
    for i in range(n):
        next_pos[s[i]] = curr_pos[i]
    return next_pos

def chk(curr_pos):
    for i in range(n):
        if curr_pos[i] not in finalpos[i%3]:
            return True
    return False


ans = 0
while chk(curr_pos):
    curr_pos = move(curr_pos)
    ans+=1
    
    tmp = tuple(curr_pos)
    if tmp in case:
        print(-1)
        break
    case.add(tmp)
else:
    print(ans)