게임이론

• 보통 이런 게임에서는, 상대에게 최대한 적은 선택지를 넘겨주는것이 최선이 되는 경우가 종종 있다. 이 게임에서는 돌을 1개만 남기고 넘겨주면, 상대는 그 한개를 제거하는 선택지밖에 남지 않는다. 이 아이디어를 염두에 두고 생각하면서 전략을 세워보자.
• 서브게임에서 선후공을 결정할 수 있는 포지션이 있다면 승리포지션이 된다는 점을 생각해보자. 현재 위치한 노드 u에는 돌이 한개도 없는 상태가 되고, u에 인접한 노드들 중에서 한개를 시작 위치로 골라서 같은 게임을 한다고 생각해보자. 각 시작 노드별로, 선공이 승리하거나 후공이 승리하거나 하는 결과는 정해져 있을것이다. 만약, 선공이 패배하고 후공이 승리하는 시작 위치 v가 있다고 한다면, 본 게임에서의 선공은 u에서 돌을 모두 제거하고 v로 이동시키면 승리할수 있다. 만약 모든 시작 위치에서 선공이 승리한다고 하면, 본 게임에서의 선공은 u에서 돌을 1개만 남기고 위치를 u에서 움직이지 않고 턴을 넘길수 있다. 후공은 u의 돌을 0개로 만들고 u에 인접한 노드중 하나로 움직일텐데, 어디로 움직이든 선공의 필승전략이 있으므로 결국 본 게임에서 선공이 승리할수 있다. 요약하면, 현재 위치한 노드에 돌이 2개 이상 있다면 선공이 항상 승리할수 있다.
• 그러면, 결국 이 게임은 누가 먼저 돌이 2개 이상인 노드에서 시작할수 있는가에 따라 결정되는 게임이 된다. 서로 돌이 1개인 노드들로만 이동하다가, 이동할수 있는 노드들 중에서 돌이 1개인 노드가 없는 사람이 패배한다. 출발점과 연결된 돌이 1개인 노드들만으로 이루어진 연결요소의 크기를 세어서, 짝수개이면 선공의 승리, 홀수개이면 후공의 승리가 된다. 돌이 1개인 노드들로 이루어진 연결요소의 크기를 찾는것은 단순한 그래프 탐색으로 O(V+E)에 찾을수 있다.
• 예외케이스는 돌이 2개 이상인 노드가 없는 경우이다. 이때는 서로 번갈아가면서 돌을 1개씩 제거하게 된다. 노드의 갯수가 홀수면 선공의 승리, 짝수면 후공의 승리이다.

"""Solution code for "BOJ 16142. 게임이론".

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

Tags: [game theory]
"""

import sys
from teflib import graph as tgraph

INF = float('inf')


def main():
    n, m, s = [int(x) for x in sys.stdin.readline().split()]
    w = [int(x) for x in sys.stdin.readline().split()]
    graph = tgraph.create_graph_from_input(n, m)
    source = s - 1

    dist = [-1 if w_i > 1 else INF for w_i in w]
    one_count = sum(1 for u in tgraph.bfs(graph, source, distances=dist))
    if one_count == n:
        is_win_pos = n % 2 == 1
    else:
        is_win_pos = one_count % 2 == 0

    print('hwy' if is_win_pos else 'sjh')


if __name__ == '__main__':
    main()

• Dependency:
  • teflib.tgraph.create_graph_from_input
  • teflib.tgraph.bfs