5227. Game of Stones
Platinum 3
문제 분석
굉장히 재밌는 문제였다.
문제를 보면 사이클이 없는 단방향 그래프가 있고, 각 노드에 돌이 있다. 각자 돌을 그래프의 간선을 따라 이동할 수 있을 때, 돌을 더 이상 움직이지 못하는 쪽이 패배하는 게임이다.
처음에는 각 노드에서부터 리프노드까지의 거리를 dfs로 구하려고 했다.
그러고 그 리프노드까지의 거리의 홀짝성을 모두 xor하면 될 것 같다는 생각이었다. 그러나 잘못 생각해도 한참 잘못 생각했음을 알았다.
풀이
리프까지의 거리를 알 필요가 전혀 없다. 만약 0->1, 1->2, 1->4, 2->3 의 그래프에서 0번 노드에 돌이 있었고 이를 1번 노드로 옮겼다면 0->1 게임판은 사라지고 1->2, 1->4, 2->3 게임판만 남게 된다.
설명이 장황한데, 그냥 각 노드에서의 그런디 수만 알면 된다는 것이었다.
간단히 dfs로 그런디 수들을 모두 구하고 각 위치에서 돌이 홀수 개만 있는 곳을 xor해주면 풀리는 문제이다.
고찰
슬슬 스프라그 그런디 문제가 질린다. 그래서 한 단계 높은 Just as Tic Tac Toe 문제를 보고 있는데, 이거... 그런디는 그냥 거들 뿐이고 FWHT라는 알고리즘을 써야하는 문제인 것 같다.
아마 다음 포스팅은 문제를 풀지 않고 FWHT에 관해 정리한 내용이 될 것 같다. 진짜 개어렵다..
풀고 있는 알고리즘 리스트(Platinum V 이상)
The Wandering Caretaker