표준 끝말잇기

돌림 단어 쌍 제거

지금까지의 승패 전파 알고리즘을 통해 우리는 최대 길이가 1인 사이클(루프)까지 고려하여 음절의 승패를 분류할 수 있었습니다. 하지만 여기서 한 걸음 더 나아가, 최대 길이가 "2"인 사이클을 분석하면 게임의 승패를 훨씬 더 깊이 이해할 수 있습니다.

'돌림 단어'란 무엇인가?

기존의 승패 전파와 가지치기를 모두 수행한 그래프를 상상해 봅시다. '톱'이라는 음절은 '톱날', '톱자루' 같은 수많은 단어가 이미 가지치기되어, 유일하게 '톱날지붕'이라는 단어 하나만 남아있습니다.

이때 플레이어가 '톱날지붕'을 말하면, 상대방은 '붕'을 받게 됩니다. 그런데 만약 상대방이 '붕어톱'이라는 단어로 즉시 받아칠 수 있다면 어떻게 될까요? 게임은 톱 → 붕 → 톱의 흐름으로 되돌아오고, 결국 '톱'에서 시작한 플레이어는 불리한 상황에 놓입니다.

이처럼 $a$ → $b$ , $b$ → $a$ 로 즉시 주고받을 수 있는 단어의 쌍을 '돌림 단어 쌍'이라고 부릅니다.

돌림 단어 쌍 제거 불변성 원리

이 돌림 단어 쌍은 매우 강력하고 놀라운 성질을 가집니다. 바로 "그래프 내의 모든 돌림 단어 쌍을 제거해도, 다른 모든 음절의 승패 여부는 전혀 바뀌지 않는다"는 것입니다.

이전의 루프 분석은 알고리즘 수행 '도중에' 적용되는 규칙이었지만, 이 성질은 승패 전파와 관계없이 게임 시작 '전에' 적용하여 그래프 자체를 단순화할 수 있는 매우 강력한 법칙입니다. 이를 수식으로 표현하면 다음과 같습니다.

그래프 $G$ 에 돌림 단어 쌍 $(a,b)$ 와 $(b,a)$ 가 존재할 때, 어떤 정점 $v$ 에 대해서도 다음이 성립합니다.

isWin $(G, v)$ = isWin $(G - (a,b) - (b,a), v)$

(isWin $(G, v)$ 는 포지션 $(G, v)$ 가 필승이면 true를 반환하는 함수)

불변성 원리에 대한 증명

이 원리의 핵심은, 돌림 단어 쌍이 '어느 한쪽에게만 유리한 필살기'가 될 수 없기 때문입니다. 어떤 플레이어가 돌림 단어의 한쪽을 사용하면, 상대방은 즉시 반대쪽 단어로 응수하여 그 효과를 완벽하게 상쇄할 수 있습니다.

더 엄밀하게 증명해 봅시다. 'A'와 'B' 두 플레이어가 있고, 돌림 단어 쌍이 제거된 작은 그래프를 $G'$ , 원래 그래프를 $G$ 라고 하겠습니다. 우리는 " $v$ 가 $G'$ 에서 필패라면, $G$ 에서도 필패이다" 라는 사실을 보일 것입니다.

가정: A가 시작하는 포지션 ( $G'$ , $v$ )는 필패입니다. 즉, B는 $G'$ 위에서 진행되는 게임의 필승 전략( $S'$ )을 알고 있습니다.
상황: 이제 A와 B가 더 큰 그래프 $G$ 에서 게임을 시작합니다. B는 자신의 필승 전략 $S'$ 를 이용해 A를 이길 수 있습니다. B의 전략은 간단합니다.
1. 만약 A가 $G'$ 에도 존재하는 '일반적인 수'를 둔다면, B는 자신의 필승 전략 $S'$ 에 따라 응수합니다.
2. 만약 A가 $G'$ 에 없는 '특별한 수', 즉 돌림 단어 $a \rightarrow b$ 를 둔다면, B는 즉시 반대쪽 단어인 $b \rightarrow a$ 로 받아칩니다.
결과: A가 특별한 수 $a \rightarrow b$ 를 사용했을 때 어떤 일이 벌어질까요?
- A가 $a \rightarrow b$ 를 말했습니다. ( $a\rightarrow b$ 엣지 소멸)
- B가 $b \rightarrow a$ 로 받아쳤습니다. ( $b\rightarrow a$ 엣지 소멸)
- 게임판은 이제 $G'$ 가 되었고, 위치는 $a$ 이며, 턴은 다시 A에게 돌아왔습니다.

결국 A가 한 행동은, 자신의 턴을 소모하여 게임판 위에서 돌림 단어 쌍을 지워버린 것과 같습니다.

A는 이제 포지션 ( $G'$ , $a$ )에서 다음 수를 두어야 합니다. 하지만 B는 원래부터 $G'$ 위의 모든 상황에 대한 필승 전략 $S'$ 를 가지고 있었습니다. A가 어떤 수를 두든, B는 $S'$ 에 따라 대응하여 승리할 수 있습니다.

따라서 A는 $G$ 에서 어떤 수를 선택하든 B를 이길 수 없습니다. $v$ 가 $G'$ 에서 필패라면, $G$ 에서도 필패인 것이죠. 이는 두 게임의 승패 여부가 완벽히 동일함을 의미합니다.

최종 알고리즘과 '루트 음절'

이 강력한 원리 덕분에, 우리는 어떤 포지션 ( $G$ , $v$ )를 분석할 때 다음의 과정을 거칠 수 있습니다.

그래프 $G$ 내의 모든 돌림 단어 쌍을 찾아 전부 제거합니다.
크기가 현저히 작아진 그래프에 대해, 앞에서 설명한 '막다른 길'과 '루프'를 이용한 승패 전파 알고리즘을 적용합니다.

이 과정을 통해 우리는 '최대 길이가 2인 사이클을 수반하는 필승/필패 정점'을 빠른 시간 내에 모두 찾아낼 수 있습니다. 이것이 저희 끝말잇기 엔진이 도달한, 신속하게 분류 가능한 음절의 최대 범위입니다.

이렇게 모든 분석을 마친 후에도 여전히 승패가 결정되지 않고 남는 음절들을 '루트 음절'이라고 부르며, 이 음절들로 이루어진 단어를 '루트 단어'라고 합니다. 현대의 수많은 끝말잇기 고수들의 대결은 바로 이 루트 음절을 서로 주고받으며, 더 복잡한 수읽기를 통해 승패를 겨루는 영역에서 펼쳐집니다.