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

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

DFS를 통해 매번 승자를 확인 한 후

지우가 먼저 K번을 이기는지를 확인할 수 있도록 했다.

지우, 경희, 민호가 내는 손동작을 번호라고 가정한 후,

다음과 같이 문제를 해결하기 위해 접근했다.

1) DFS 함수에서 현재 지우의 순번을 기준으로 이제까지 내지 않았던 번호를 지정한다. 

  (만약 현재 가위바위보를 하는 사람이 지우가 아니라면 생략) 

2) 경기에 참여하는 인원 2명의 순번을 확인한다.

3) 경기에 참여하는 인원의 순번에 따라 내는 번호를 확인한 후, 주어진 상성에 대한 정보를 통해 승자를 확인한다.

 (만약 무승부라면 민호, 경희, 지우의 우선순위에 따라 승자를 정해준다)

4) 지우가 N번째 순번까지 모든 번호를 사용해도 K번을 이기지 못했거나

    경희나 민호가 K번을 이겼다면 더이상 진행하지 않고 1),2),3)번을 반복 실행한다.

5) 지우가 K번을 이겼거나 모든 탐색을 마쳤다면 종료한다. 

예제 입력을 한 뒤에 오답을 계속해서 출력해서 질문 검색을 참고하다가 중요한 실수 2가지를 나중에야 알게되었다.

첫 번째로 지우,경희,민호가 각 라운드마다 내는 번호가 있을 때 

자신이 참여하지 않는 경기는 라운드를 고려하면 안되는 것이다.

다음과 같은 순서로 경기가 진행되었다고 가정하자.

1경기 => 지우 vs 경희 (지우 승)

2경기 => 지우 vs 민호 (민호 승)

3경기 => 경희 vs 민호 (경희 승)

이때, 지우와 경희, 민호의 승패 여부와 상관없이 다음 라운드를 4라운드라고 생각했지만

실제로는 지우와 경희, 민호 모두 1라운드씩만 진행을 한 것이다. 즉, 자신이 참여하는 경기 기준으로 순번 처리를 잘 해줘야 한다.

두번째로 새로 경기에 참여하는 인원이 경기 진행 순서상 뒤로 오는 것이 아닌,

항상 민호, 경희, 지우 순으로 경기 진행 순서가 뒤로 고정되어 있다.

경희와 민호의 경기에서 경희가 승리를 한 뒤, 다음 경기에서 지우와 경기를 할 때

새로 참가하는 지우가 아닌, 경희의 진행 순서가 뒤에 있다고 생각하고 문제를 풀어야 한다.

#include <iostream>
using namespace std;
 
int N,K;
int ans=0;
int A[11][11]={0};
int JKM[3][21]={0}; //지우,경희,민호의 순번에서 내는 손동작 번호
int WIN[3]={0}; //지우,경희,민호의 승리 회수
int TURN[3]={0}; //지우,경희,민호의 참여 회수(순번)
 
bool jw_number(int num){
    for(int i=0;i<TURN[0];i++)
        if(JKM[0][i]==num)
            return true;
    
    return false;
}
 
void dfs(int p1,int p2){
    
    //지우가 K번 이겼을 때
    if(WIN[0]==K){
        ans=1;
        return;
    }
    
    //경희나 민호가 K번 이겼을 때
    if(WIN[1]==K || WIN[2]==K)
        return;
    
    //지우의 순번동안 N번을 모두 냈거나 이미 정답 나왔을 때
    if(TURN[0]>N || ans==1)
        return;
    
    
    //지우의 순번에서 손동작 번호 정하기
    for(int num=1;num<=N;num++){
        
        //만약 지우가 없다면 반복문 타지 않고 한번만 실행
        if(p1!=0 && p2!=0){
            num=N;
        }else{
            
            //지우의 순번 전까지(TURN[0]) num 있었는지
            if(jw_number(num))
                continue;
            
            JKM[0][TURN[0]]=num; //지우의 순번에서 내는 손동작 번호 설정
        }
        
        int winner=0;
        int turn1=TURN[p1]; //p1이 참여하는 경기 순번
        int turn2=TURN[p2]; //p2가 참여하는 경기 순번
        
        int n1=JKM[p1][turn1];
        int n2=JKM[p2][turn2];
        
        if(A[n1][n2]==2)    winner=p1;
        else if(A[n1][n2]==0)   winner=p2;
        else winner=(p1<p2)? p2:p1; // 우선순위 = 민호(2) > 경희(1) > 지우(0)
 
        TURN[p1]++;
        TURN[p2]++;
        WIN[winner]++;
        dfs(winner,3-(p1+p2));
        WIN[winner]--;
        TURN[p1]--;
        TURN[p2]--;
    }
 
}
 
int main(){
    
    cin>>N>>K;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            cin>>A[i][j];
    
    for(int i=0;i<20;i++)
        cin>>JKM[1][i];
    
    for(int i=0;i<20;i++)
        cin>>JKM[2][i];
    
    dfs(0,1);
    cout<<ans<<endl;
    
    return 0;
}