분석의 확장: 루프(Loop)를 이용한 승패 판별

이전의 '사이클 없는 승패 전파' 알고리즘은 많은 음절의 승패를 결정하지만, 한계가 있습니다. 바로 스스로에게 되돌아오는 루프(loop)가 포함된 경우입니다. 이 루프를 분석하면 더 많은 음절의 승패를 알아낼 수 있습니다.

1. 하나의 루프가 유일한 퇴로일 경우

예를 들어, '몫'으로 시작하는 단어에 '몫몫', '몫돈', '몫자리', '몫일'이 있다고 가정해봅시다. 만약 '몫돈', '몫자리', '몫일'이 모두 상대방의 필승으로 이어지는 '나쁜 수'라면, '몫'에 있는 플레이어는 이 단어들을 선택해서는 안 됩니다. 유일한 전략적 선택은 '몫몫'을 말하여 상대방을 다시 '몫'으로 보내는 것입니다.

상대방은 '몫'을 받았지만, 선택지는 모두 '나쁜 수'밖에 없으므로 결국 패배하게 됩니다. 따라서 이 상황을 유도할 수 있는 원래의 '몫'은 필승 음절입니다.

이러한 상황은 이전 알고리즘으로는 판별할 수 없습니다. 나쁜 수들이 '가지치기'로 제거되고 나면 '몫'에는 '몫몫'이라는 루프만 남아 '막다른 길'이 아니기 때문입니다.

2. 여러 개의 루프만 있을 경우: 홀짝 게임

한 발 더 나아가, 루프가 여러 개인 경우는 어떨까요? 어떤 음절 'a'에서 나가는 길이 'a'로 되돌아오는 루프밖에 없다고 가정해 봅시다. 이 상황은 두 플레이어가 루프를 하나씩 번갈아 사용하는 게임이 됩니다.

• 루프가 홀수 개일 때: 내가 먼저 첫 번째 루프를 사용하고, 상대가 두 번째, 내가 다시 세 번째... 결국 마지막 루프는 내가 사용하게 됩니다. 따라서 이 게임은 내가 이기므로, 해당 음절은 필승입니다.
• 루프가 짝수 개일 때: 같은 원리로, 마지막 루프는 상대방이 사용하게 됩니다. 따라서 이 게임은 내가 지므로, 해당 음절은 필패입니다.

규칙 3: 다른 길은 없고 루프만 존재할 때, 루프의 개수가 홀수이면 필승, 짝수이면 필패이다.

---

최종 수정: '막다른 길' 개념의 확장

위의 논리를 반영하여, 우리는 알고리즘의 시작점인 '막다른 길 찾기' 과정을 다음과 같이 확장합니다. 승패를 판별하고 가지치기를 하는 대상은 이제 두 종류입니다.

1. 진짜 막다른 길 (엣지 0개): 나가는 엣지가 하나도 없는 정점은 이전과 같이 필패로 확정하고 제거합니다.
2. 루프만 있는 길 (엣지 N개): 나가는 엣지가 모두 자기 자신으로 돌아오는 루프뿐인 정점은, 루프의 개수가 홀수이면 필승으로, 짝수이면 필패로 확정하고 제거합니다.

이렇게 확장된 규칙으로 '막다른 길'들을 먼저 처리하고 나면, 나머지 '필패 → 필승 전파' 과정은 이전과 동일하게 진행하여 전체 그래프의 승패를 더욱 정확하게 분석할 수 있습니다.