※ 이 공부기록은 부정확한 내용이 다수 포함되어있을 수 있다. 또한 이 글은 정보 전달이 주 목적이 아닌 개인적인 기록용이어서 체계적으로 내용이 정리되어 있지 않을 수 있다. 읽는이의 양해를 바란다.
들어가기 전에
공부기록03까지 쓰고 나서 글쓴이는 Semi-Game Cup 4 오프라인 대회를 준비하고 참가했다. 지난 대회와 마찬가지로 이번 대회에서도 B와 E에서 구현 과정에 문제가 있었고 많은 WA를 받았지만, 그래도 결국 문제 해결에는 성공해 5문제를 풀어낼 수 있었다. 특히 E는 구현 전에 생각한 두 가지 그래프 표현 방식을 섞어 구현해서 디버깅에 애를 먹었었다. 다음에는 이런 일이 발생하지 않도록 구현을 시작하기 전에 간단한 주석이라도 달아놓아야겠다.
대회 이름이 이름이다보니 이번 대회를 대비하면서 여러 게임이론과 관련된 주제를 공부했는데, 그 중 Green Hackenbush의 해법은 흥미로운 내용이라고 생각했고, 우리말로 된 좋은 증명 자료를 찾기 어려워 관련 공부 기록을 남겨두기로 생각했다.
Hackenbush
Hackenbush는 Conway가 고안한 게임 중 하나로, blue edge, red edge, green edge의 세 가지 종류의 간선으로 구성된 그래프 위에서 Left와 Right의 두 플레이어가 진행하는 게임이다. 이 그래프의 몇몇 정점은 ground 정점으로 지정되어 있으며, 모든 정점에서는 적어도 하나의 ground 정점과 이어지는 경로(간선의 색은 신경쓰지 않는다.)를 찾을 수 있다.
이제, Left와 Right는 차례를 번갈아가며 게임을 진행한다. 자신의 차례에 Left는 blue edge 또는 green edge 중 정확히 하나의 간선을 골라 제거해야 하며, Right는 red edge 또는 green edge 중 정확히 하나의 간선을 골라 제거해야 한다. 플레이어가 간선을 제거하고 나면, 어떠한 ground 정점과도 이어지는 경로가 없는 모든 정점 및 그 정점을 포함하는 모든 간선을 지운다. 자신의 차례에 지울 수 있는 간선이 없는 플레이어가 패배한다.
Hackenbush를 구성하는 그래프 \(G\)가 유한하다면, 매 차례가 지날 때마다 \(G\)의 간선의 개수는 줄어들 뿐 늘어나거나 유지될 수는 없으므로 게임은 항상 끝나며 승패가 결정됨을 확인하자. 이 아래로 Hackenbush를 이루는 그래프는 유한하다고 가정한다.
Green Hackenbush
Green Hackenbush는 blue edge와 red edge 없이 green edge만으로 구성된 Hackenbush를 의미한다. Green Hackenbush의 가장 큰 특징은 Left와 Right가 할 수 있는 행동의 집합이 서로 같은 impartial game이라는 것이다. 일반 Hackenbush에서는 blue edge와 green edge가 존재하므로 impartial game이 될 수 없다.
이 아래로 blue edge와 red edge를 언급할 일이 특별히 없으므로, 이제부터 색에 대한 특별한 언급이 없는 간선은 모두 green edge로 간주하자.
이제 Green Hackenbush는 최선을 다할 시 선공과 후공 중 누가 이길지 알아보자.
Green Hackenbush Forest
먼저 ground 정점와 이어진 간선은 많아야 하나이며 다른 모든 정점과 이어진 간선은 많아야 두 개인 단순한 형태를 생각해보자. 이 형태의 경우 주어진 green hackenbush는 각 ground 정점과 이어진 각 maximal subgraph의 간선의 개수를 token의 개수로 한 nim game으로 치환할 수 있다. 따라서 이 형태의 green hackenbush는 nim game과 같은 방법으로 선공과 후공의 승패를 판단할 수 있다.
위 형태에서 ground 정점과 이어진 간선의 개수 제약은 지우더라도 ground 정점을 split하는 것으로 어렵지 않게 nim game으로 다시 모델링할 수 있다는 점을 확인하자. 물론 반대로 다시 ground 정점을 합쳐도 전체 게임의 grundy number는 변하지 않는다.
이제 ground 정점이 하나이고 이를 root로 하는 트리 구조의 green hackenbush를 해결해보자. 이 경우는 다음과 같은 lemma를 활용하면 어렵지 않게 해결할 수 있다.
lemma: ground 정점이 하나이고 이를 root로 하는 트리 구조의 green hackenbush graph를 \(G\)라 하고, 이 그래프의 grundy number를 \(n\)이라 하자. 이 때, 정점 하나와 이 정점을 기존 ground 정점과 잇는 간선 \(e\)을 추가하고, 새로 추가한 정점을 ground 정점으로 하며 기존 ground 정점을 일반 정점으로 하는 새로운 그래프 \(G'\)의 grundy number는 \(n+1\)이다.
증명은 아래와 같다.
강한 수학적 귀납법(strong induction)을 이용한다.
\(G\)의 정점의 개수가 \(k\) 미만일 때 위 lemma가 성립한다고 가정하자. 이 가정 하에서 \(G\)의 정점의 개수가 \(k\)일 때 위 lemma가 성립함을 보이면 증명이 끝난다.
\(G\)의 정점의 개수를 \(k\)개라고 하고, grundy number를 \(n\)이라 하자. 그리고 위 lemma와 같이 수정한 그래프를 \(G'\)라 하자.
이 때, \(G'\)에서 간선 \(e\)를 제거하면 ground 정점을 제외한 \(G'\)의 모든 정점과 간선이 지워지므로 다음 상태는 grundy number가 0이 된다.
그리고 \(G\)에서 \(G\)를 구성하는 간선을 하나 지우면 \(G\)의 정점의 개수는 \(k\)보다 작아지므로 (\(G\)는 트리이기 때문) 위 lemma를 적용할 수 있다는 점을 활용하면, \(G'\)에서 \(e\)가 아닌 간선을 지웠을 때 얻을 수 있는 다음 상태의 grundy number에는 1부터 \(n\)까지는 확실하게 있으며, \(n+1\)은 확실하게 없음을 알 수 있다.
모든 간선을 제거하는 경우를 고려했을 때, 다음 상태로 가능한 grundy number에는 0부터 \(n\)까지는 확실하게 있으며, \(n+1\)은 확실하게 없음을 알 수 있다. 따라서 \(G'\)의 grundy number는 \(n+1\)이다. □
위 lemma를 활용하면 ground 정점이 하나인 tree 형태의 그래프의 형태로 주어지는 green hackenbush를 tree DP와 같이 해결할 수 있다. 또한, 모든 maximal subtree에 ground 정점이 정확히 하나씩만 있는 green hackenbush forest 또한 각 maximal subtree의 grundy number를 이용하여 해결할 수 있다.
Fusion Principle
이제 forest 형태가 아닌 \(G\)에 대하여 green hackenbush의 grundy number의 값을 구해보자. 이는 fusion principle이라고 불리는 다음 정리를 활용하는 것으로 얻을 수 있다.
fusion principle: \(G\)의 임의의 cycle에 대하여, 이 cycle에 속한 모든 정점을 하나의 정점으로 합쳐 얻은 새로운 그래프 \(G'\)의 grundy number는 \(G\)의 grundy number와 같다.
여기서 cycle의 모든 정점을 합친다는 것은 사이클에 포함된 정점의 집합의 크기가 1이 될 때까지 이 집합에서 두 정점을 골라 다음과 같은 fusion 연산을 하고 새로 생성한 정점을 집합에 추가하는 일을 반복하는 것을 말한다.
fusion: 두 정점 \(x\)와 \(y\)의 fusion은 새로운 정점 \(xy\)를 만들어 \(x\)와 \(y\)를 끝점으로 갖는 모든 간선의 대응되는 끝 점을 \(xy\)로 변경한 뒤 \(x\)와 \(y\)를 지운다. 이 과정에서 \(x\)와 \(y\)를 잇는 간선, \(x\)의 self-loop, \(y\)의 self-loop는 각각 \(xy\)의 self-loop가 된다.
다음은 fusion principle의 증명이다. 명제는 단순하지만 증명이 상당히 기므로, 대략적인 흐름을 먼저 소개한다.
(0) green hackenbush에 대한 다른 principle들을 먼저 소개한다.
(1) 귀류법을 사용하여 cycle을 fusion할 시 grundy number에 변화가 생기는 그래프의 존재를 가정한다.
(2) 그 중 (조건을 만족하는) 가장 작은 그래프가 unicyclic한 형태가 되어야 함을 보인다.
(3) 그러나 이 (조건을 만족하는) 가장 작은 unicyclic한 그래프는 (유일한) cycle을 fusion해도 grundy number가 변하지 않음을 보여 (1)의 가정이 틀림을 보인다.
(4) (3)의 과정에는 간단하게 처리하기 어려운 한 가지 예외 경우가 있다. 이 예외경우를 해결하는 알고리즘을 소개하고 증명한다.
아래는 fusion principle의 증명에 활용하는 두 principle인 colon principle과 parity principle의 소개와 증명이다.
colon principle: ground 정점이 유일한 그래프 \(G\)와 ground가 아닌 한 정점 \(v\)를 생각하자. 이 때, 두 connected subgraph \(G'\)와 \(H\)가 (1) 공통 정점은 \(v\) 뿐이며 (2) 공통 간선은 존재하지 않고 (3) 두 그래프의 정점 집합의 합집합은 \(G\)의 정점의 집합과 같고 (4) 두 그래프의 간선 집합의 합집합은 \(G\)의 간선의 집합과 같다다는 성질을 가지고 있다고 가정하자. 이 때, \(G\)에서 \(v\)를 제외한 \(H\)의 구성요소를 제거하고, 대신 원래 \(H\)에서 \(v\)를 ground취급하였을 때의 \(H\)의 grundy number와 같은 grundy number를 갖는 다른 그래프 \(H'\)의 ground를 \(v\)에 붙여도 \(G\)의 grundy number는 변하지 않는다.
증명: 기존의 그래프 \(G\)에서 위의 과정을 따라 새로 만든 그래프를 \(K\)라 하자. \(G\)와 \(K\)를 같이 놓고 동시에 게임을 진행할 때 후공이 이긴다는 것을 보이면 두 게임의 grundy number가 같다는 것을 증명할 수 있다.
선공은 (1) \(G\) 또는 \(K\)에서 \(G'\)에 속한 간선과 대응되는 간선을 지우거나, (2) \(H\) 또는 \(H\')에 속한 간선과 대응되는 간선을 지우는 두 가지 행동 중 하나를 해야 한다.
(1) 선공이 \(G'\)에 속한 간선과 대응되는 간선을 제거한다면 후공은 다른 게임의 대응되는 \(G'\)간선을 따라서 제거할 수 있다. 이 과정에서 선공이 \(H\) 또는 \(H'\)을 ground와 연결되지 않게 만들었다면 대응되는 후공의 행동도 \(H'\) 또는 \(H\)를 ground와 연결되지 않게 만든다.
(2) 선공이 \(H\) 또는 \(H'\)에 속한 간선과 대응되는 간선을 제거하면, 후공은 \(H\)와 \(H'\)의 grundy number가 기존에 같았으므로 다시 \(H\)와 \(H'\)의 grundy number가 같아지게 하는 행동을 항상 할 수 있다.
따라서 선공이 어떤 행동을 하더라도 후공은 대응되는 행동을 할 수 있다. 즉, 후공이 항상 승리한다□
parity principle: green hackenbush forest의 grundy number의 parity(2로 나눈 나머지)는 green hackenbush forest를 구성하는 간선의 개수의 parity와 같다.
증명: green hackenbush forest의 grundy number 계산 과정은 두 grundy number의 xor과 앞선 lemma를 이용하여 간선을 따라 이동하며 grundy number를 1 증가시키는 것으로 이루어져 있다. 이 두 과정은 모두 parity를 보존한다.□
아래는 fusion principle의 증명이다.
fusion principle이 거짓이라고 가정하자. 그렇다면 어떤 cycle이 있어서 그 cycle을 fusion했을 때 grundy number에 변화가 있는 그래프가 존재한다. 그러한 그래프 중 가장 간선의 개수가 적은 그래프, 그러한 그래프도 여럿이라면 그 중 가장 정점의 개수가 가장 적은 그래프 중 하나를 골라 \(G\)라고 하자.
이 때, \(G\)의 특징을 다음과 같이 좁혀나갈 수 있다.
(1) \(G\)의 ground 정점은 유일하다.
그렇지 않다면 두 ground 정점을 fusion하여 정점이 더 적으면서 위의 성질을 만족하는 그래프를 항상 얻을 수 있기 때문이다.
(2) \(G\)의 임의의 cycle 위의 두 정점을 fusion하면 grundy number가 달라진다.
그렇지 않다면 그 두 정점을 fusion하여 정점이 더 적으면서 위의 성질을 만족하는 그래프를 얻을 수 있기 때문이다.
(3) \(G\)의 임의의 두 정점 \(x\)와 \(y\)에 대하여 \(x\)와 \(y\)를 잇는 세 개의 edge-disjoint path는 존재할 수 없다. 즉, \(G\)는 cactus graph이다.
증명: \(G\)의 어떤 두 정점 \(x\)와 \(y\) 사이에 세 개의 edge-disjoint path가 존재한다고 가정하자. 그리고 \(G\)에서 \(x\)와 \(y\)를 fusion한 그래프를 \(H\)라 하자. (2)에 의해 \(G\)와 \(H\)의 grundy number는 달라야한다. 따라서, 두 green hackenbush \(G\)와 \(H\)를 같이 놓고 플레이하면 선공이 이겨야한다. 그러나 이 게임은 후공이 이기는 게임이다. 선공이 어떤 간선을 고르더라도 후공이 \(G\)와 \(H\) 사이의 대응되는 에지를 고르는 것으로 항상 응수할 수 있기 때문이다.
(4) \(G\)의 모든 사이클은 ground 정점을 지난다.
증명: ground 정점을 지나지 않는 cycle이 있다고 가정하자. 이 때, 이 cycle 위의 정점 중에는 cycle에 속하는 간선을 지나지 않으면서 ground까지 이어질 수 있는 정점이 존재할 것이다.
case 1) 그러한 정점이 둘 이상 있다고 가정하자. 그 정점들 중 두 정점을 \(x\)와 \(y\)라 하자. 이 때, \(x\)와 \(y\)에서 각각 ground 정점으로 이어지는 각 경로는 가정에 따라 cycle과 edge-disjoint하며, 두 경로가 (각각 \(x\)와 \(y\)쪽을 기준으로) 처음으로 만나는 정점 \(z\)가 존재한다(늦어도 ground에서는 만나므로). 이제 \(x\)와 \(y\)는 \(z\)를 통하는 cycle과 disjoint한 path 하나와 cycle을 통한 path까지 해서 세 개의 edge-disjoint path를 가지게 된다. 이는 (3)에 모순이다.
case 2) 그러한 정점이 유일하다고 가정하자. 그렇다면 이 정점을 기준으로 ground를 포함하며 앞서 정한 cycle은 포함하지 않는 maximal한 connected component \(X\)와 그 외 모든 정점(앞서 정한 cycle을 온전히 포함한다)으로 구성된 connected component \(H\)의 두 connected component로 그래프를 나누어 생각할 수 있다. 3에서 언급한 cactus graph의 형태를 생각해보면 이는 자연스러울 것이다. 한편, \(H\)의 간선 개수는 \(G\)보다 적으므로, 가정에 의해 \(H\)에 속한 앞서 정한 cycle을 fusion하여 얻는 그래프 \(H'\)의 grundy number는 \(H\)와 동일하다. 따라서 colon principle에 의해 \(G\)에서 이 cycle은 fusion해도 grundy number가 변하지 않음을 알 수 있다. 이는 가정에 모순이다.
(5) \(G\)의 cycle은 유일하다.
증명: cycle이 여러 개 존재한다고 가정해보자. 그 중 하나는 fusion하면 grundy number가 변하는 것으로 고르고, 다른 하나는 아무 cycle이나 하나 고를 수 있다. 이 때, (4)에 따라 두 cycle은 (유일한) ground 정점을 공유하고, (3)에 따라 두 cycle은 ground 정점 외에는 공통 정점이 존재하지 않는다. 한편, ground 정점을 통하지 않으면 두 cycle 사이에는 이동할 수 있는 path가 존재하지 않아야 하는데, 이유는 그러한 path가 존재한다면 각 cycle과 각각 한 정점에서만 만나는 path가 존재하고, 그 path의 양 끝점 사이에는 3개의 edge-distinct path가 생겨 (3)에 모순되기 때문이다. 따라서, \(G\)가 나타내는 게임은 서로 다른 ground 정점을 갖는 두 개의 게임처럼 생각할 수 있게 되는데, 각 게임의 간선의 개수는 \(G\)의 간선의 개수보다 적으므로 어떤 cycle을 fusion해도 grundy number는 변하지 않아야 한다. 이는 모순이다.
따라서 \(G\)는 정확히 하나의 ground 정점과 이 정점을 포함하는 하나의 cycle을 갖는 그래프, 즉 ground 정점이 사이클에 포함된 unicyclic graph이어야 한다. 이제 \(G\)의 (유일한) cycle을 fusion해도 grundy number가 변하지 않음을 보이면 증명이 끝난다.
\(G\)의 (유일한) cycle을 fusion하여 얻는 그래프를 \(H\)라 하자. 이제 두 그래프를 같이 놓고 게임을 진행할 때 후공이 이긴다는 것을 보일 것이다.
선공이 할 수 있는 행동은 (1) \(G\)의 cycle에 포함되지 않은 간선(또는 그와 대응되는 \(H\)의 간선) 지우기, (2) \(G\)의 cycle에 포함되는 간선 지우기, (3) \(H\)의 원래 cycle에 포함되어 있던 간선 지우기의 세 가지가 있다.
(1)의 경우, 그에 대응되는 다른 그래프의 간선을 지우면 \(G\)의 간선의 개수가 줄어들어 정의에 따라 grundy number의 변화 없이 \(G\)의 cycle을 fusion할 수 있게 되는데, 그렇게 얻은 그래프는 \(H\)와 같으므로 선공이 패배한다.
(2)의 경우, 이제 주어진 게임은 총 홀수개의 간선으로 이루어진 green hackenbush forest가 된다. 따라서 parity principle에 의해 이 green hackenbush forest의 grundy number는 0이 될 수 없으며, 후공이 승리한다.
(3)의 경우, cycle을 이루는 간선의 개수가 짝수개라면 후공도 \(H\)에서 원래 cycle에 포함되어 있던 간선을 따라 지워 (1) 또는 (2)의 선택을 선공에게 강요할 수 있다. 홀수개이면 이와 같은 전략을 사용할 수 없다.
따라서, cycle을 이루는 간선이 홀수개이고 선공이 \(H\)에서 원래 cycle에 포함되어 있던 간선을 지웠을 때의 필승법을 찾아 문제를 해결할 수 있다. 그 방법은 다음과 같다.
방법을 설명하기 전에 지금의 상황을 다시 한번 정리하면, ground 정점이 cycle에 속해있으며 cycle을 이루는 간선이 홀수개인 unicycle graph \(G\)와 이 그래프의 cycle을 fusion한 그래프 \(H\)를 같이 놓고 게임을 시작한 뒤, 선공이 \(H\)에서 기존 \(G\)의 cycle에 포함되어 있던 간선 하나를 지운 뒤 후공이 필승전략을 찾는 상황이다.
(0) 먼저, 주어진 그래프에서 "cycle에 포함된 간선"을 포함하지 않는 각각의 maximal한 subtree들을 같은 grundy number를 갖는 일자형 그래프로 바꾸자. colon principle에 의해 이 과정에서 grundy number의 변화는 없다.
(1) \(G\)의 cycle을 구성하는 각 간선에 라벨\(A\)와 라벨\(B\)를 다음 규칙에 따라 붙인다. 단, ground 정점과 이어진 cycle의 두 간선은 인접하지 않은 것으로 생각한다.
<규칙> 인접한 두 간선의 공통정점에 붙어 있는 일자형 그래프의 길이(=grundy number)가 홀수이면 두 간선은 같은 라벨을 갖고, 짝수이면 두 간선은 다른 라벨을 갖는다.
(2) 일반성을 잃지 않고, 위와 같이 라벨을 붙였을 때 홀수개의 간선에 붙은 라벨을 A, 짝수개의 간선에 붙은 라벨을 B라 하자. 이 때, 라벨 \(B\)가 붙은 간선은 제거시 전체 게임의 grundy number가 \(2 \mod 4\)가 되므로 라벨 \(B\)가 붙은 간선은 후보가 될 수 없음을 알 수 있다. 라벨 \(A\)가 붙은 간선은 제거시 전체 게임의 grundy number가 \(0 \mod 4\)이다.
(참고) (2)에서 언급한 2번째 비트의 parity 성질의 증명 흐름:
이 부분은 단순계산의 성격이 더 강하므로 전체적인 흐름만 적어둔다.
같은 라벨이 붙은 두 간선 사이의 정점에는 grundy number가 \(1 \mod 4\) 또는 \(3 \mod 4\)인 일자형 그래프가, 다른 라벨이 붙은 두 간선 사이의 정점에는 grundy number가 \(0 \mod 4\) 또는 \(2 \mod 4\)인 일자형 그래프가 붙어있다. 이 때, ((1)) 먼저 어떤 사이클의 간선을 끊어도 위의 각 정점의 트리의 grundy 수의 2번째 비트는 전체 게임의 grundy number의 4로 나누었을 때의 2번째 비트에 영향을 주지 않음을 보이고, ((2)) A와 B를 임의로 나열한 문자열에서 인접한 두 문자를 교환하더라도 grundy number의 4로 나눈 나머지에는 변화가 없음을 보이고, ((3)) 따라서 cycle에서 지우는 간선이 \(A\)인지 \(B\)인지 경우를 나누고 해당 간선의 양옆으로 A와 B의 개수의 parity가 어떻게 되는지 경우를 나누어 A...AB...B꼴로 나열시킨 뒤 grundy number가 어떻게 계산되는지를 확인하는 것으로 증명할 수 있다.
(3) 이제 \(G\)에서 라벨 \(B\)가 붙은 각각의 간선에 대하여 해당 간선이 잇는 두 정점을 fusion한다. 그리고 (0)에서 한 것과 같이 "cycle에 포함된 간선"을 포함하지 않는 각각의 maximal한 subtree들을 같은 grundy number를 갖는 일자형 그래프로 바꾸자. 그리고 각 일자형 그래프의 길이를 절반으로(소수점이 발생할 경우 버림을 시행) 바꾼다. 이 과정을 거쳐 변화한 \(G\)의 간선을 지웠을 때의 grundy number는 기존 \(G\)의 대응되는 간선을 지울 때 얻게 되는 grundy number의 절반이 된다. 이 내용의 증명은 그래프를 직접 그려 몇 번 해보면 어렵지 않으므로 생략한다.
(참고) 모든 라벨이 모두 같은 경우는 사용하지 않은 라벨이 짝수개 사용되었다고 생각할 수 있으므로 어떤 간선도 fusion되지 않고 일자형 그래프의 길이만 변화한다.
(4) 과정 (2)와 과정 (3)을 cycle의 간선이 오직 하나 남을 때까지 반복한다. 이 때, 남은 cycle의 간선 중 하나를 지우는 것이 후공의 필승전략이 됨은 어렵지 않게 알 수 있다.
따라서 \(G\)와 \(H\)를 같이 놓고 하는 게임은 선공이 패배한다. □
여담으로, 위의 증명과정을 따라가면 (이길 수 있을 경우) 선공이 이기기 위해 어떤 간선을 지워야 하는지도 이론상 구할 수는 있다.
\(G\)에 (self-loop를 제외한) cycle이 없어질 때까지 (self-loop를 제외한) 임의의 cycle을 골라 fusion하는 것을 반복하면 결국 \(G\)의 각 biconnected component가 하나의 노드로 압축됨을 알 수 있다. 또한 각 self-loop는 그냥 그 정점에서 (self-loop마다) 새 정점을 만들어 이은 것과 똑같이 취급할 수 있다. 따라서 fusion principle을 활용하면 일반 green hackenbush를 green hackenbush forest 문제로 환원할 수 있다.
마무리
결국 green hackenbush의 grundy number는 증명은 몰라도 방법만 알면 biconnected component, tree DP의 개념을 이용하여 구할 수 있다. Semi-Game Cup 4 준비가 아니었다면 green hackenbush도 그냥 넘겼을 것 같지만, 그래도 이를 구현해보는 것은 구현이 약한 글쓴이에게 좋은 연습이 되었다. 구현 연습삼아 green hackenbush 문제를 풀어보는 것은 어떨까?
관련 문제
green hackenbush forest는 관련 내용을 잘 모르더라도 대회장에서 충분히 유도할만 하고, 실제로 대부분의 green hackenbush 관련 문제는 이정도 선에서 그치는 정도로 출제되는 것으로 보인다.
일반 그래프에서의 green hackenbush는 풀이가 올바르다는 증명이 비직관적이고 길어서 그런지 출제 사례가 드문 것 같다. 다만, green hackenbush의 풀이 자체는 PS/CP에서 자주 사용되는 내용만을 활용하여 해낼 수 있으므로, 일단 풀이가 한 번 알려지면 종종 출제될 수도 있을 법하다고 생각한다.
직접적으로 Green Hackenbush Tree를 해결할 것을 요구하는 문제이다.
주어진 문제는 trie의 형태를 한 Green Hackenbush Forest로 모델링할 수 있다. 새로운 단어를 추가할 때마다 trie의 grundy number를 재계산하면 시간복잡도가 너무 커지므로, 적절히 각 subtree의 grundy number를 저장 및 업데이트해 문제를 해결하자.
직접적으로 일반 그래프에서의 Green Hackenbush를 해결할 것을 요구하는 문제이다.
오래된 문제라서 입력 설명이 불친절한데, 입력으로 들어오는 테스트케이스의 수는 20 이하, 각 테스트케이스에서 주어지는 그래프의 정점과 간선의 개수는 각각 50000 이하로 잡고 문제를 해결해보자. 또한, 서로 다른 두 정점을 잇는 중복된 간선(multiple edges)이 입력으로 들어올 수도 있고, self-loop 또한 입력으로 들어올 수도 있다는 점에 유의하자.
참고 자료
Winning Ways for Your Mathematical Plays (Elwyn R. Berlekamp, John H. Conway, Richard K. Guy)
On Numbers and Games (John H. Conway)
https://en.wikipedia.org/wiki/Hackenbush
https://www.math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Bartlett.pdf
https://simonrs.com/eulercircle/cgt2024/agastya-hackenbush.pdf