[백준] 16986 - 인싸들의 가위바위보 ✌️✊✋ / 골드 3 / 부루트포스

BAEKJOON Logo

 

 

 

 

Contents

 

---

1.  문제🔥

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

문제

문제를 요약하자면, 3명이서 인싸 가위바위보를 할 때의 우승자를 정하기 위한 구체적인 방식은 아래와 같습니다. (편의상 참가자 3명을 A, B, C)

1. A, B, C는 게임 시작 전 우승을 위해 필요한 승수와 경기 진행 순서를 미리 합의합니다. 경기 진행 순서가 A, B, C라고 가정하겠습니다.
2. 먼저 A와 B가 경기를 진행해 승자를 결정합니다. 만약 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주합니다. 즉 A와 B가 같은 손동작을 내면 B의 승리, A와 C가 같은 손동작을 내면 C의 승리, B와 C가 같은 손동작을 내면 C의 승리입니다.
3. 이전 경기의 승자와 이전 경기에 참여하지 않은 사람이 경기를 진행해 승자를 결정합니다.
4. 특정 사람이 미리 합의된 승수를 달성할 때까지 3을 반복합니다.
5. 합의된 승수를 최초로 달성한 사람이 우승합니다.

침 vs 펄 vs 풍

침펄풍이 싸우는 경우의 예시입니다.

 

1) 예제 입출력❄️

예제입출력

첫 줄에 손동작 수(N)과 우승에 필요한 승수(K)가 주어집니다. 그다음에 N개의 줄 동안 인접 행렬 형태로 가위바위보의 우선순위가 주어집니다. i행 j열의 숫자가 2이면 i가 j를 이기는 경우, 0이면 지는 경우, 1이면 비기는 경우입니다. 그 다음 2줄에는 경희와 민호가 참여하는 경기에서 20번 낼 손동작이 주어집니다.

 첫번째 예시에선 승수 K가 2이기 때문에, 경우는 지우가 서로 다른 손동작으로 2번만 이기면 됩니다. 처음에 2를 낸 경희와 싸우기 때문에 2를 이기는 3을 내고, 두 번째에는 3을 낸 민호와 싸우며, 4를 이기는 1을 내면 바로 승리하므로, 출력은 지우가 서로 다른 손동작을 내서 우승할 수 있으므로, 1을 출력합니다.

 

2. 핵심 논리☢️

지우가 낼 수 있는건 항상 다른 손 모양이므로, N개를 어떤식으로 낼 건지 permutations를 통해 순열을 구하고, 그 순열로 게임을 진행했을 때 우승하는지 아닌지를 모두 탐색하는 것이 핵심입니다.

3. 풀이 코드✅

import sys
from itertools import permutations
input=sys.stdin.readline
N,K=map(int,input().split())
board = [list(map(int,input().split())) for _ in range(N)]
p2 = list(map(int,input().split())) # 경희
p3 = list(map(int,input().split())) # 민호
jiwo = [i+1 for i in range(N)] # 지우

def DFS(py1, py2, index, win, player):
    global result
    if win[0] == K: # 지우가 이긴경우
        result = 1
        return
    if win[1] == K or win[2] == K: # 민호 or 지우가 이긴경우
        return
    if index[0] == N: # 지우가 낼 손모양이 없는 경우
        return
    py3 = 3 - (py1+py2) # 이전 출전했던 선수들의 합을 3에서 빼면 다음출전할 선수->py3
    pv1 = player[py1][index[py1]]-1 # py1이 낼 손모양 -> 손모양 인덱스는 0부터니까 1빼주기
    pv2 = player[py2][index[py2]]-1
    index[py1] += 1 # py1 한번 냈으니까, 인덱스 증가 -> 다음에 낼 손모양 결정
    index[py2] += 1
    if board[pv1][pv2] == 2 or (board[pv1][pv2] == 1 and py1 > py2): # py1이 이긴 경우
        win[py1] += 1
        DFS(py1, py3, index, win, player)
    elif board[pv1][pv2] == 0 or (board[pv1][pv2] == 1 and py1 < py2): # py2가 이긴 경우
        win[py2] += 1
        DFS(py2, py3, index, win, player)

for p1 in permutations(jiwo, N):
    player = [p1,p2,p3] # 지우, 경희, 민호가 낼 전체 소모양 이중리스트
    index = [0,0,0] # 지우, 경희, 민호가 어떤 손모양을 낼지
    win = [0,0,0] # 지우, 경희, 민호가 각각 몇번 이겼는지
    result = 0 # 지우가 이길수있는지
    DFS(0,1,index,win,player)
    if result == 1:
        print(1)
        break
else:
    print(0)

손동작 수(N)과 우승에 필요한 승수(K)를 입력받습니다. 가위바위보의 우선순위가 담긴 인접 행렬을 board에 이중 리스트로 입력받습니다. 경희와 민호의 20회 동안 낼 손동작을 p2, p3에 입력받고, 지우가 낼 수 있는 손동작 개수를 jiwo에 저장합니다. 그리고 맨 아래 for문에서 permutations를 돌며 jiwo가 N개의 손동작을 내는 순열을 p1으로 반복합니다. player에 각 경기별 지우, 경희, 민호가 낼 전체 손 모양 이중 리스트를 저장하고, index에는 각 게임 시점에서 지우, 경희, 민호가 어떤 손모양을 낼지 인덱스를 트래킹 합니다. win에는 각 게임 시점에서 지우, 경희, 민호가 몇 번 이겼는지를 저장합니다. result에는 지우가 N개 서로 다른 손동작으로 우승했는지를 저장하는 최종 출력 변수입니다. 

 각 for문에서 DFS를 돌며, player, index, win에 대해 지우가 이겼는지를 탐색합니다. 지우가 이긴경우 전역변수화된 result에 1을 넣고 return으로 DFS가 종료되도록 합니다. 지우가 이기지 않은 경우는 그냥 return으로 DFS가 종료되도록 합니다. py3 = 3 - (py1 + py2) 부분은 3번째 플레이어는 현재 게임에서 싸우는 py1과 py2를 더한 것을 3에서 빼서 알 수 있습니다. py1과 py2는 각각 0, 1, 2중 하나이기 때문입니다. pv1에 py1이 낼 손 모양의 인덱스를 저장하고, pv2에는 py2가 낼 손 모양의 인덱스를 저장합니다. 그리고 한번 게임을 진행했기 때문에 index에서 py1과 py2에 += 1을 해줍니다. 그리고 py1이 이긴 경우와 py2가 이긴 경우를 나눠서 DFS를 재귀 호출해줍니다.

 마지막에 for문 뒤에 else문이 있는데, 이는 for else 문이라는 문법입니다. for문 내부에서 break를 만나지 않았다면 else문이 실행될 것이고, for문 내부에서 break를 만났다면 뒤에 else문은 실행되지 않습니다.

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/BaekJoon/blob/master/jupyter/16986_%EC%9D%B8%EC%8B%B8%EB%93%A4%EC%9D%98_%EA%B0%80%EC%9C%84%EB%B0%94%EC%9C%84%EB%B3%B4.ipynb

GitHub - netsus/BaekJoon: Algorithm Problem solving

Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/