문제 태그

• 스프라그 - 그런디
• Graph
• 컴포넌트 홀짝 판정

문제 요약

입력

• 연결된 무방향 그래프와 시작 정점이 주어진다.
• 모든 정점에는 초기에 돌이 1개 이상 있다.
• 모든 정점에는 자기 자신으로 가는 루프가 있다.

출력

• 두 사람이 최적으로 플레이할 때 승자를 출력한다.

목표 재정의

• 시작 정점에서 출발하는 상태가 선공 필승인지 판정한다.

예시 워크스루

예시는 정점이 2개이고 시작 정점이 1이며 돌 개수가 1, 2인 경우를 본다.

1. 초기 상태에서 정점 1의 돌은 1개라서 반드시 1개를 제거해야 한다.
2. 정점 1이 0이 되면 돌이 남아 있는 정점 2로 이동해 턴을 넘긴다.
3. 상대는 정점 2에서 2개를 전부 제거할 수 있으므로 마지막 돌을 가져간다.