사용자 도구

사이트 도구


ps:problems:boj:29457

Игра с графом

ps
링크acmicpc.net/…
출처BOJ
문제 번호29457
문제명Игра с графом
레벨실버 4
분류

게임이론

시간복잡도O(1)
사용한 언어Python 3.11
제출기록31120KB / 40ms
최고기록40ms
해결날짜2024/02/02

풀이

  • 그래프가 분리되지 않도록 하는 엣지들을 지워나가다가, 그것이 불가능해지면 진다.
  • 어떤 엣지를 지워도 그래프가 분리되게 되는 것은 그래프가 트리가 되는 시점이고, 그때의 남은 엣지는 n-1개이다.
  • 결국 서로 엣지를 1개씩 줄여나가다가, 자기 차례에 남은 엣지가 n-1개가 되는 사람이 지게 되는 것이므로, 처음 m-(n-1) 의 홀짝성에 따라 승리 플레이어가 결정된다. m-(n-1)이 홀수이면 선공 승리, 짝수이면 후공 승리이다. 실제 엣지가 어떻게 주어지는지는 볼 필요도 없다. 그래서 원래는 인풋 데이터를 읽는데만 O(m)이 걸리겠지만, 여기에서는 인풋 데이터를 다 읽을 필요조차 없다.
    • 출력해야 하는 것은 승리하는 플레이어가 아니라 패배하는 플레이어라는 데에 주의하자
  • 무승부가 나올 일이 없으므로, 무승부를 출력하는것은 페이크인가 싶은데.. 그런 경우가 있다. 처음에 노드가 1개밖에 없는, 그래서 당연히 엣지는 하나도 없는 경우이다. 사실 이 경우는, 문제에서 규칙이 명확하게 주어지지 않은거라서 결과가 무승부가 되는지 선공의 패배가 되는지가 불명확한 감이 있다. 하지만 이 경우에는 무승부로 출력해야 통과된다

코드

"""Solution code for "BOJ 29457. Игра с графом".

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

Tags: [game theory]
"""


def main():
    n, m = [int(x) for x in input().split()]
    if n == 1:
        print('Draw')
    else:
        print('Alice' if (m - (n - 1)) % 2 == 0 else 'Bob')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
X L H H S
 
ps/problems/boj/29457.txt · 마지막으로 수정됨: 2024/02/02 12:57 저자 teferi