이분 유향 그래프 모델

끝말잇기에 두음 법칙이 추가되면, 게임의 양상은 훨씬 더 흥미롭고 복잡해집니다. 이제 플레이어는 단어를 선택하기 전에 '두음 법칙을 적용할 것인가'라는 추가적인 전략적 선택에 직면하게 됩니다.

예를 들어, 상대방이 '관례'를 말해 나에게 '례'라는 음절이 주어졌다고 합시다. 나는 두 가지 선택을 할 수 있습니다.

이처럼, 한 턴의 과정이 '음절 변환 → 단어 선택'의 2단계로 확장됩니다.

이 새로운 규칙은 모든 음절에 두 가지 다른 역할과 가치를 부여합니다. 예를 들어, '례'라는 글자는 이제 두 가지 상태로 구분되어야 합니다.

이 둘의 전략적 가치는 완전히 다를 수 있습니다. 예를 들어, '끝 음절' 례는 '예'라는 강력한 선택지를 포함하므로 필승의 위치일 수 있지만, '첫 음절' 례는 사용할 수 있는 단어가 적어 루트 음절(승패를 알 수 없는)일 수 있습니다.

따라서 우리는 이 두 상태를 명확히 구분하여 모델링해야 합니다.

기존의 그래프 모델은 음절의 이런 이중적인 역할을 표현할 수 없습니다. 그래서 우리는 이분 유향 그래프(Bipartite Directed Graph)라는 새로운 구조를 도입합니다.

이분 그래프란, 간단히 말해 모든 정점이 두 개의 분리된 집단으로 나뉘어 있고, 모든 엣지는 한 집단에서 다른 집단으로만 향하는 그래프를 의미합니다. 같은 집단 내의 정점끼리는 직접 연결되지 않습니다.

끝말잇기 모델에서는 이 두 집단을 다음과 같이 정의합니다.

이 두 집단을 연결하는 엣지 역시 두 종류로 나뉩니다.

두음 법칙 엣지 (영구적): '끝 음절'에서 '첫 음절'로 향하며, 두음 법칙의 적용 관계를 나타냅니다. (예: (끝 음절)례 → (첫 음절)예, (끝 음절)례 → (첫 음절)례). 이 엣지는 '규칙' 자체이므로, 게임 중에 사용해도 사라지지 않습니다.
단어 엣지 (소모성): '첫 음절'에서 '끝 음절'로 향하며, 실제 단어를 의미합니다. (예: (첫 음절)예 → (끝음절)절 은 '예절'이라는 단어). 이 엣지는 단어를 한 번 사용하면 사라지므로, 게임 중에 제거됩니다.

이 새로운 모델 위에서 한 턴의 흐름은 다음과 같이 명확하게 정의됩니다.

포지션 (Position): ( $G$ , $v_{last}$ )
- $G$ 는 현재 단어들이 포함된 전체 이분 그래프.
- $v_{last}$ 는 상대방에게 받은 '끝 음절' 정점.
한 수 (A Move): 플레이어는 두 개의 엣지를 순서대로 통과합니다.
1. 현재 위치 $v_{last}$ 에서 두음 법칙 엣지를 타고, 자신이 사용할 '첫 음절' 정점 $v_{first}$ 로 이동합니다.
2. $v_{first}$ 에서 단어 엣지 $e$ 를 타고, 다음 상대에게 넘겨줄 '끝 음절' 정점 $v_{last\_next}$ 로 이동합니다.
상태 변화 (State Transition): 단어 엣지 $e$ 가 사용되었으므로, 다음 상대방의 포지션은 ( $G-e$ , $v_{last\_next}$ )가 됩니다. 오직 단어 엣지만 사라진다는 점이 중요합니다.