16986. 인싸들의 가위바위보

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

import java.util.Scanner;
 
// 손가락 가지수가 최대 9개입니다.
// 즉, 지우가 낼 수 있는 가지수가 9개 뿐이므로 아무리 많아도 9!개의 가지수가 존재하게 됩니다.
// 따라서 재귀함수를 통한 백트래킹을 구현해도 아무런 문제가 없기 때문에 해당 방식으로 구현했습니다.
// 시간복잡도 : O(N!)
 
public class Main{
    static boolean result = false; // 최종 결과
    static int N, M; // N : 손가락 가지수 , M : 목표 승수
    static int pick[][]; // 각 플레이어의 차례별로 낼 모양을 저장한 배열
    static int arr[][]; // 각 손가락 모양별 상성을 저장할 배열
 
    /////////////////////// user1과 user2가 낸 모양에 따라 승자의 번호를 리턴하는 함수 //////////////////////////
    static int rsp(int pick1, int pick2, int user1, int user2) {
        if (pick1 != pick2) {
            if (arr[pick1][pick2] == 2) {
                return user1;
            }
            else if (arr[pick1][pick2] == 0) {
                return user2;
            }
        }
        else {
            return Math.max(user1, user2);
        }
        return -1;
    }
    
    /////////////////////// dfs를 시행할 함수 ///////////////////////////
    static void solution(int user1, int user2, int winCount[], int turnCount[], boolean used[]) {
        // user1과 user2는 유저의 번호, winCount는 해당 상태에서 각 플레이어의 승 수, turnCount는 해당 상황에서 각 플레이어가 몇번째 차례를 맞이했는지
        // used는 모든 손가락 가지수에 대해 지우가 사용했는지 / 안했는지를 저장할 배열
        
        // 지우가 먼저 목표 승수에 도달
        if (winCount[0] == M) {
            result = true;
            return;
        }
        // 지우가 아닌 다른 사람이 먼저 목표 승수에 도달
        else if (winCount[1] == M || winCount[2] == M) {
            return;
        }
        
        int userNext = 3 - user1 - user2;
        // 이번 게임이 끝나고 다음으로 만날 상대를 저장하는 변수
        // 참가자 번호가 지우 : 0 , 경희 : 1, 민호 : 2이므로 비트마스크를 이용하여 다음 상대를 구할 수 있다.
 
        // user1에 지우가 있을 경우 / user2에 지우가 있을 경우 / 지우가 없을 경우를 나눠서 실행했습니다.
        // user1과 user2를 정렬한다면 user2가 지우인 경우를 확인할 수고를 덜 수 있습니다 !
        
        if (user1 == 0) { // user1이 지우라면
            for (int i = 1; i <= N; i++) { // 1번부터 모든 손가락 가지수에 대해
                if (!used[i]) { // 사용하지 않은 것이 남아있다면
                    int winner = rsp(i, pick[user2][turnCount[user2]],0,user2);
                    // user2가 이번 턴에 낼 손가락 종류와 아직 사용하지 않은 손가락 종류를 냈을 때 승자를 뽑습니다.
                    winCount[winner]++;
                    turnCount[user2]++;
                    used[i] = true;
                    solution(winner, userNext, winCount, turnCount, used); // 냈다는 가정하에 solution함수 실행 !
                    winCount[winner]--;
                    turnCount[user2]--;
                    used[i] = false;
                    // 다시 안낸 상태로 복귀 ( 돌아올 경우 다른 손가락 가지수를 찾아서 실행하게 됩니다. )
                }
            }
        }
        else if (user2 == 0) { // user2가 지우인 경우는 마찬가지
            for (int i = 1; i <= N; i++) {
                if (!used[i]) {
                    int winner = rsp(pick[user1][turnCount[user1]], i, user1, 0);
                    winCount[winner]++;
                    turnCount[user1]++;
                    used[i] = true;
                    solution(winner, userNext, winCount, turnCount, used);
                    winCount[winner]--;
                    turnCount[user1]--;
                    used[i] = false;
                }
            }
        }
        else { // user1과 user2가 모두 지우가 아닐 때
            int winner = rsp(pick[user1][turnCount[user1]], pick[user2][turnCount[user2]], user1, user2);
            // 각각 현재 낼 차례인 손가락을 이용하여 승자를 뽑습니다.
            winCount[winner]++;
            turnCount[user1]++;
            turnCount[user2]++;
            solution(winner, userNext, winCount, turnCount, used);
            // 주의할 점 ! 결국 이 함수도 끝에 도달할 경우 return되면서 돌아올 것이기 때문에
            // 아래와 같이 반드시 원래 상태로 돌려줘야 합니다. (이것떄문에 맞왜틀..)
            winCount[winner]--;
            turnCount[user1]--;
            turnCount[user2]--;
        }
    }
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        N=scan.nextInt();
        M=scan.nextInt();
        pick = new int[3][21];
        arr=new int[12][12];
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                arr[i][j]=scan.nextInt();
            }
        }
        for (int i = 0; i < 20; i++) {
            pick[1][i]=scan.nextInt();
        }
        for (int i = 0; i < 20; i++) {
            pick[2][i]=scan.nextInt();
        }
        int winCount[] = new int[3];
        int turnCount[] = new int[3];
        boolean used[] = new boolean[11];
        solution(0, 1, winCount, turnCount, used);
        if(result) System.out.println(1);
        else System.out.println(0);
    }
}