시뮬레이션에서 사이클 감지하기

일부 모의 실행에서는 1조 번처럼 엄청나게 많은 단계가 지난 뒤의 상태를 묻습니다. 한 번에 한 단계씩 진행하면 제한 시간 안에 끝나지 않습니다. ⏳

가능한 상태의 수가 제한되어 있다면 모의 실행은 결국 같은 상태를 다시 만나게 됩니다. 그때부터는 순환이 영원히 반복됩니다.

경로에는 순환으로 들어가는 꼬리가 있고, 그 뒤에는 반복되는 고리가 있습니다. 고리를 찾으면 수십억 단계를 빠르게 건너뛸 수 있습니다.

각 상태를 사전에 저장하고, 그 상태를 처음 본 단계 번호와 연결하세요. 같은 상태를 다시 보면 순환을 알아낼 수 있습니다.

각 단계 전에 현재 상태가 이미 확인된 상태 집합에 있는지 확인하세요. 이미 있다면 방금 순환이 완성된 것입니다.

길이는 현재 단계에서 이 상태를 처음 본 단계의 번호를 뺀 값입니다. 그만큼의 단계가 지나면 상태가 정확히 다시 돌아옵니다.

꼬리 부분을 뺀 다음, 남은 단계 수를 순환 길이에 대한 나머지로 계산하세요. 이제 아주 조금 남은 단계만 모의 실행하면 됩니다.

순환 시작점에서 그 남은 단계만큼 모의 실행하세요. 최종 상태는 정확히 N번째 단계의 상태와 일치합니다.

사전의 키는 해시 가능해야 하므로 저장하기 전에 목록을 튜플로 바꾸세요. 변경 가능한 상태는 키가 될 수 없습니다.

상태가 너무 커서 저장할 수 없다면 Floyd의 거북이와 토끼 알고리즘이 두 개의 포인터를 사용해 추가 기억 공간을 거의 쓰지 않고 순환을 찾습니다.

순환 감지는 불가능해 보이는 1조 단계의 반복을 수천 단계로 바꿉니다. 반복을 알아차리는 것이 이 방법의 핵심입니다.

현재 상태를 단계 s에서 처음 보았고, 지금은 단계 t에 있습니다.

상태가 반복되면 각 상태를 사전에 기록하고, 순환 길이를 찾은 뒤, 나머지 연산으로 건너뛰고 남은 단계만 모의 실행하세요. 🚀