끝말잇기의 수학적, 알고리즘적 분석

이 문서의 최종 목표는 두음 법칙이 적용되는 끝말잇기의 복잡한 구조를 수학적으로 모델링하고, 그 필승/필패 조건을 판별하는 알고리즘을 탐구하는 것입니다.

두음 법칙이 추가된 게임은 '음절 변환'이라는 새로운 선택지가 생기면서, 그 구조와 분석 알고리즘이 근본적으로 달라집니다. 이 복잡한 모델을 바로 이해하기는 어렵기 때문에, 우리의 탐구는 두 단계로 진행됩니다.

1. 기초 다지기: 먼저 두음 법칙이 없는 간소화된 '표준 모델'을 통해 승패를 분석하는 핵심적인 알고리즘들을 익힙니다.
2. 목표 분석: 그 다음, 배운 알고리즘들을 '두음 법칙 모델'에 맞게 재정의하고 확장하여 최종 목표를 분석합니다.

즉, '표준 끝말잇기'의 분석은 그 자체가 목적이 아니라, 더 복잡한 '두음 법칙 끝말잇기'의 분석 알고리즘을 정복하기 위한 필수적인 준비 과정입니다.

---

두 모델의 핵심 차이점

두음 법칙의 존재 여부가 왜 이렇게 중요한 차이를 만드는지는 아래의 모델 비교표를 통해 명확히 확인할 수 있습니다.

항목	표준 끝말잇기 (학습용 모델)	두음 법칙 끝말잇기 (최종 목표)
게임 흐름	1단계: 단어 선택	2단계: 규칙 적용 → 단어 선택
음절의 역할	단일 역할 (끝 글자 = 첫 글자)	이중적 역할 (단어의 '끝 음절' vs 단어의 '첫 음절')
그래프 모델	일반 유향 그래프	이분 유향 그래프
정점	음절	끝 음절 집합과 첫 음절 집합으로 분리
엣지	단어 엣지 (소모성)	규칙 엣지 (영구적) + 단어 엣지 (소모성)
포지션	($G$, $v$)	($G$, $v_{last}$)
구조적 복잡성	낮음	높음
기본 루프 형태	1-사이클 ($v \rightarrow v$)	2-사이클 ($v'_{first} \rightarrow u_{last} \rightarrow v'_{first}$)
'돌림 단어' 제거	단순 제거 가능: 그래프에서 쌍을 이루는 단어 엣지를 제거해도 승패 불변	엄격한 조건부 제거: '경로 열등성' 조건을 만족하는 쌍만 제거 가능
승패 전파 규칙	필패→필승, 필승→필패의 2가지 단순 전파	역할(끝/첫)과 상태(승/패)에 따른 4가지 복합 전파 규칙