[백준] 인싸들의 가위바위보

https://www.acmicpc.net/problem/16986

16986번: 인싸들의 가위바위보

완전 탐색, 백트래킹으로 풀 수 있는 문제입니다. 침착맨이 다르게 낼 수 있는 모든 손동작의 경우의 수 n!에 따른 경기 결과를 직접 시뮬레이션해보면 됩니다. 제 풀이는 침착맨이 낼 수 있는 모든 손동작의 경우를 만든 다음 시뮬레이션을 하기 때문에 시간이 조금 더 걸리지만 백트래킹으로 직접 라운드마다 낼 수 있는 손동작을 그때 그때 지정하는 방식으로 풀면 조금 더 짧은 시간안에 풀이가 가능합니다.

 

import sys
from itertools import permutations
from collections import deque

CHIM = 0
PERL = 1
POONG = 2

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, k = tuple(map(int, input().split()))

superior = [[0] * (n + 1)] + [
    [0] + list(map(int, input().split()))
    for _ in range(n)
]


if n < k:
    print(0)
    sys.exit(0)

perl = list(map(int, input().split()))
poong = list(map(int, input().split()))

hands = [x for x in range(1, n + 1)]


def simulate(dqs):
    winner = CHIM
    next = PERL

    wins = [0] * 3
    while True:
        # 더 이상 낼 수 없는 경우
        if not dqs[winner]:
            return False
        # 더 이상 낼 수 없는 경우
        if not dqs[next]:
            return False

        # 전판 승자의 손동작
        handOfWinner = dqs[winner].popleft()
        # 상대의 손동작
        handOfNext = dqs[next].popleft()

        result = superior[handOfWinner][handOfNext]

        # 전판 승자가 이긴 경우
        if result == 2:
            wins[winner] += 1
            next = 3 - winner - next

        # 비긴 경우
        elif result == 1:
            # 전판 승자가 순서상 앞인 경우, 진 것과 같이 처리
            if winner < next:
                wins[next] += 1
                tmp = next
                next = 3 - winner - next
                winner = tmp
            # 전판 승자가 순서상 뒤인 경우, 이긴 것과 같이 처리
            else:
                wins[winner] += 1
                next = 3 - winner - next

        # 전판 승자가 진 경우
        else:
            wins[next] += 1
            tmp = next
            next = 3 - winner - next
            winner = tmp

        # 누군가 k번 승리했고
        if wins[winner] == k:
            # 우승자가 침착맨인 경우
            if winner == CHIM:
                return True
            # 펄, 풍인 경우
            else:
                return False

# 침착맨이 낼 수 있는 모든 손동작 O(9!)
for chim in permutations(hands, n):
    ret = simulate([
        deque(chim),
        deque(perl),
        deque(poong)
    ])
    
    # 모두 다른 손동작을 내서 이길 수 있는 경우
    if ret:
        print(1)
        sys.exit(0)

print(0)