Hackenbush에 대한 간단한 튜토리얼을 쓰려고 하는데, 내가 이걸 잘 아는 거는 아니라서 (...) 증명 및 깊이 있는 이론들은 (ordinal 등장 등) 대부분 생략하고 알고리즘 문제 풀이에 써먹을 수 있는 부분들만 간략히 추려서 쓰려고 한다. 자세한 증명은 구글에 검색하면 자료가 매우 많으니 찾아보는 것을 추천한다 :)

 

Hackenbush 게임은 두 명이서 하는 게임으로, 여러 가지 버전들이 존재하지만 근본적인 목표는 똑같다.



위 그림과 같이, 일종의 그래프가 지면에 연결되어 있는 상태에서 게임이 시작된다. 

각 플레이어는 순서대로 간선 하나를 제거하는데, 이때 더 이상 지면에 연결되지 않게 되는 간선들은 모두 삭제된다.

일반적인 룰에서는 (normal play convention) 간선을 제거하지 못하게 되는 플레이어가 패배한다.

간선이 무한히 많은 경우도 존재하지만, 여기에서는 유한한 개수의 간선이 존재한다고 가정한다.

그러면 게임이 확실하게 Sprague-Grundy 방식으로 분석이 가능해진다. 이를 위해서 다음 Principle을 활용한다.


Colon Principle: 그래프 $G, H, K$가 있다. $H, K$의 Grundy 값이 같다면, $G$의 정점 $x$에 $H$를 붙인 그래프와 $x$에 $K$를 붙인 그래프의 Grundy 값이 동일하다. 그러므로, 한 점에서 '가지치기'가 되는 그래프가 있다면, 각 가지들의 Grundy 값의 XOR에 해당하는 길이의 일직선을 붙이는 것으로 가지들을 대체할 수 있다. 이를 통해서 트리 그래프에 대한 분석을 끝낼 수 있다. DFS를 돌면서 서브트리의 Grundy 값을 순서대로 계산하면 된다.


Fusion Principle: 두 정점이 한 사이클 위에 놓인다면 (지면을 하나의 노드로 본다) 두 점을 하나로 합쳐도 Grundy 값이 변하지 않는다. 

이때 두 점을 잇는 간선들은 self-loop가 된다. 이 성질을 이용하면, 임의의 그래프에 대한 Grundy 값을 구할 수 있다.

실제로 이를 활용하는 문제는 본 적이 없지만, 아무튼 이를 이용하면 기본 Hackenbush에 대한 분석은 끝이다.


연습문제: Project Euler 400 Fibonacci Tree Game, BOJ 13893 Dictionary Game

두 문제 다 Hackenbush에 대한 이해와 적당한 구현을 (DP/Trie 등) 통해서 해결할 수 있다. Fusion Principle은 필요 없다.


Blue-Red Hackenbush는 조금 색다르다. 이제는 각 간선마다 누가 자를 수 있는지가 둘 중 한 명으로 정해져 있다.

각 플레이어를 Blue/Red라고 하고, Blue 간선은 Blue만, Red 간선은 Red만 자를 수 있도록 한다.

이때는 각 연결 컴포넌트 $G$에 대하여, 그 컴포넌트의 값 $v(G)$를 다음과 같이 재귀적으로 정할 수 있다.

아무것도 없는 그래프의 경우 값은 자명하게 $0$이다. $G$가 nonempty라고 가정하자.

$b$를 Blue가 만들 수 있는 상태 $G'$ 중 $v(G')$의 최댓값이라 하자. 불가능한 경우 $-\infty$.

$r$을 Red가 만들 수 있는 상태 $G'$ 중 $v(G')$의 최솟값이라 하자. 불가능한 경우 $\infty$.

만약 $b < n < r$인 정수 $n$이 존재한다면, $v(G)$는 해당하는 정수 $n$ 중 $0$에 가장 가까운 것이다. 

그렇지 않다면, $v(G)$는 $b < x < r$을 만족하는 유리수 $x$ 중 분모가 $2$의 거듭제곱인 것 중에서 분모가 최소인 것이다. 


또한, 독립적인 그래프 $G, H$에 대하여 $v(G+H) = v(G) + v(H)$가 성립한다.

만약 $v(G) > 0$이라면 Blue가 승리, $v(G) < 0$이라면 Red가 승리, $v(G)= 0$이라면 후공 승리가 된다.


이 게임에 대한 직관적인 이해를 원한다면 stonejjun의 블로그를 찾아보는 것을 추천한다.


이걸 모두 짬뽕한 Blue-Red-Green Hackenbush도 있는데, 이건 진짜 무서워 보인다 ㅋㅋ


연습문제: BOJ 13409 Black and White Boxes, BOJ 18945 조직된 ㄱ폭탄 게임

13409는 Hackenbush 값을 계산한 다음 Meet In The Middle을 하면 간단하게 해결할 수 있다.

18945는 몇 가지 관찰을 한 다음, 문제를 Blue-Red Hackenbush로 변형하여 해결할 수 있다.


이 글의 진짜 목적 중 하나가 18945의 풀이를 적는 것이니, 여기에 소개한다.

각 게임을 독립적인 Blue-Red Hackenbush 게임으로 보고, 그에 대응하는 값을 계산하자. 

그러면 남은 쿼리들은 전부 단순한 point update range query 문제가 되므로, 펜윅/세그먼트 트리를 이용하여 계산할 수 있다. 

그러니 문제 난이도의 99%는 각 게임을 Blue-Red Hackenbush 게임으로 변환하는 것에서 나온다. 


일반성을 잃지 않고 A 폭탄이 하나 존재한다고 가정하자. 그러면 B 폭탄을 3가지 종류로 나눌 수 있다.

종류 1: A 폭탄이 터지면 강제로 제거되는 B 폭탄들

종류 2: 터뜨리면 A 폭탄이 터지게 되는 B 폭탄들

종류 3: A 폭탄과 서로 interact 할 수 없는 (즉, 하나가 터져도 다른 하나가 터지지 않음) B 폭탄들


이 게임판에서 A가 할 수 있는 행동은 단순히 A 폭탄 하나를 터뜨리는 것 뿐이다. 

B가 할 수 있는 행동은 다양한데, 실제로 고려해야 하는 것은 몇 가지 없음을 알 수 있다.

우선 종류 3의 폭탄과 같은 경우에는 애초에 A 폭탄이 터지던 말던 상관이 없기 때문에, 최대한 마지막에 터뜨리는 것이 좋다. 

물론, 자신이 터뜨린 폭탄에 의해 자신의 다른 B 폭탄이 쓸데없이 터지지 않도록 순서를 잘 정해서 터뜨려야 한다.

종류 2의 폭탄은 터뜨린다면 강제적으로 종류 1의 폭탄 중 남아있는 것은 무조건 터지게되며, 경우에 따라서 종류 3의 폭탄 역시 터질 수 있다. 

그러니 A 폭탄을 제거할 목적으로 종류 2의 폭탄을 터뜨린다면 종류 3의 폭탄을 최소한으로 터뜨리도록 하는 폭탄을 하나 찾아서 그걸 터뜨려야 한다.  

종류 1의 폭탄은 터뜨린다면, 다른 종류 1의 폭탄을 터뜨리지 않도록 행/열 순서를 잘 잡아서 순서대로 터뜨려야 한다.


이를 종합하면, 다음과 같은 Blue-Red Hackenbush 그림을 그릴 수 있다. A가 Red, B가 Blue라고 하자.



그래프가 특수한 형태를 가진다. 그러니, 이와 같은 경우에서 Hackenbush 값은 아예 closed form 식을 통해서도 구할 수 있다.

나는 DP를 이용하여 위에서 설명한 규칙을 직접 적용하는 방식으로 구현했다. 분수를 다루기 귀찮으니, 적당히 큰 2의 거듭제곱을 곱해줘서 다루면 편하다. 

'PS > 수학 계열 PS' 카테고리의 다른 글

8월의 PS 일지 - Part 3  (0) 2020.08.10
8월의 PS 일지 - Part 1  (0) 2020.08.04
5월의 PS 일지 - Part 1  (0) 2020.05.16
4월의 PS 일지 - Part 5  (0) 2020.05.02
4월의 PS 일지 - Part 4  (1) 2020.04.25