백준 16986 - 인싸들의 가위바위보

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

"지우는 경희와 민호의 행동 패턴을 빅데이터로 분석해 인싸 가위바위보를 하는 중 경희와 민호의 차례가 왔을 때 이들이 낼 손동작의 순서를 정확히 알고 있다. 그래서 마음만 먹으면 전승 우승이 가능하지만 경기를 흥미진진하게 이끌기 위해 인싸 가위바위보를 할 때 모든 손동작을 다르게 내고 싶어한다."

'지우는 ... 모든 손동작을 다르게 내고 싶어한다' 해당 내용은 중요한 포인트 중 하나인데 넘어갈 뻔했다.. 처음에 이것을 생각하지 않고 중복을 포함한 20개의 순열을 뽑았더니 절대 통과하지 못할 것 같아 문제를 다시 읽은 후에 발견할 수 있었다. 해당 문장의 포인트는 N개의 손동작이있으면 지우는 서로다른 손동작 N개를 뽑아야한다. 3개의 손동작이 있으면 [1,2,3], [1,3,2] ..... 의 순열을 뽑으면 된다. 뽑은 순열을 바탕으로 게임을 진행하는데
순서가 정말 정말 중요하다.. 지우,경희 민수순으로 항상 정해져있다.

ex)

R1 지우 - 경희 (지우승)
R2 지우 - 민수 (민수승)
R3 경희 - 민수 (민수승)

위 예제와 같이 순서를 지켜야한다. 처음에 저런 순서를 지키지 않고 아래와 같이 이긴 사람이 앞으로 오게 해서 삽질을 엄청나게 했다.... 순서가 가장 중요하다!!

R1 지우 - 경희 (지우승)
R2 지우 - 민수 (민수승)
R3 민수 - 경희 (민수승)

내 풀이는 처음에 항상 지우와 경희가 시함을 한다. 이 후 둘의 차례를 증가시켜주고 이긴쪽에 카운트를 증가해준다. 지우와 경희가 시함해서 지우가 이기면 지우와 민수가, 경희가 이기면 경희와 민수를 배틀 순서에 넣어준다. 이후 반복문을 돌려 위와 동일하게 player 순서를 큐에서 꺼내와서 대결하고 getBattleOrder(..) 함수를 통해 순서(지우, 경희, 민수)를 지켜준다.
이 후 지우의 승수가 K개가 되면 정답을 1로 바꿔준다. N<K 일 경우 서로다른 손동작이 아니게 되므로 항상 0이 된다.

코드

# 지우, 경희, 민호 순으로 경기를 진행

#지우의 가위바위보를 뽑는다. 중복 x 순서 중요!
from collections import deque

N, K = map(int, input().split())
jiwo = []
minho = []
kyoung = []
rules = []
global ans 
visited = [False] * (N+1)

ans = 0
for i in range(N):
    rule = list(map(int, input().split()))
    rules.append(rule)
for i in range(2):
    tmp_player_act = list(map(int, input().split()))
    if i ==0:
        kyoung = tmp_player_act
    else:
        minho = tmp_player_act
        
def getBattleOrder(p, next_player):
    if p < next_player:
        return (p,next_player)
           
    return (next_player,p)


def getNextPlayer(p1,p2):
    for i in range(1,4):
        if i !=p1 and i!=p2:
            return i
    return 0
# 가위바위보
def check(jiwo):
    global ans 
    win = [0] * 3
    players_turn = [0] * 3
    orders = deque()
    players_act = []
    players_act.append(jiwo)
    players_act.append(kyoung)
    players_act.append(minho)
    #처음은 무조건 지우랑 경희랑한다
    if rules[jiwo[players_turn[0]]-1][kyoung[players_turn[1]]-1] == 2:
        #지우가 이기면 민수랑
        orders.append((1,3))
        win[0]+=1
    else:
        #지우가 지거나 비기면 경희랑 민수랑
        orders.append((2,3)) 
        win[1]+=1
    # 턴 증가
    players_turn[0]+=1
    players_turn[1]+=1
    while(orders):
        p1,p2 = orders.popleft()
        if win[1] == K or win[2] == K:
            break
        elif win[0] == K:
            ans = 1
            break
        if players_turn[0] >= N:
            break
        if rules[players_act[p1-1][players_turn[p1-1]]-1][players_act[p2-1][players_turn[p2-1]]-1] == 2:
            win[p1-1]+=1

            next_player = getNextPlayer(p1,p2)

            orders.append(getBattleOrder(p1,next_player))
            
        else:
            win[p2-1]+=1

            next_player = getNextPlayer(p1,p2)

            orders.append(getBattleOrder(p2,next_player))
            

        players_turn[p1-1]+=1
        players_turn[p2-1]+=1
    return
def dfs(pick):
    if ans == 1:
        return
    if pick == N:
        check(jiwo)
        return
    for i in range(1,N+1):
        if not visited[i]: 
            visited[i] = True
            jiwo.append(i)
            dfs(pick+1)
            jiwo.pop()
            visited[i] = False

if N<K:
    print(0)
else:
    dfs(0)
    print(ans)