A Tree Game

• 트리 위에서 돌을 이동시키는 형태의 게임의 변형이라고 봐도 된다.
• 번갈아가면서 이동시키는게 아니라, 번갈아가면서 한명은 에지 하나에 이동불가 마크를 추가하고, 한명은 돌을 이동시킨다. 차수가 1인 노드까지 이동시키는데에 성공하면 승리.
• 처음에 돌이 놓인 노드가 루트 노드가 되도록 트리를 만들면, 항상 자식노드로만 이동하는것이 최적 방법이 되므로 계산이 깔끔해진다.
  • 리프노드는 승리포지션이다.
  • 자식노드중에 승리포지션이 두개 이상인 노드도 승리 포지션이다. (승리 포지션으로 가는 에지 한개를 막아도 다른 승리 포지션으로 이동 가능하므로)
    • 역으로, 자식노드중에 승리포지션이 한개 이하면 패배포지션이다.
• 이제 간단한 트리dp로, 루트 노드가 승리포지션인지 계산해주면 끝. 시간복잡도는 O(n)
• 주의해야할 예외처리가 두개 있다.
  • 시작 노드의 차수가 1인 경우 → 이때는 무조건 승리
  • 주어진 트리가 노드 1개짜리인 경우 → 차수가 0이니까 승리할수 없고, 이동할곳이 없으니까 패배한다.

"""Solution code for "BOJ 33416. A Tree Game".

- Problem link: https://www.acmicpc.net/problem/33416
- Solution link: http://www.teferi.net/ps/problems/boj/33416

Tags: [game theory]
"""

from teflib import tree as ttree

ROOT = 0


def main():
    n, tree = ttree.create_tree_from_input()

    if n == 1:
        print('0')
        return
    if len(tree[ROOT]) == 1:
        print('1')
        return

    dp = ttree.dp_on_tree(
        tree,
        ROOT,
        lambda dp_ch, _: len(dp_ch) == 0 or dp_ch.count(True) >= 2,
    )
    print('1' if dp[ROOT] else '0')


if __name__ == '__main__':
    main()

• Dependency: teflib.tree.dp_on_tree