[BOJ] 16986번 인싸들의 가위바위보

개요

전체탐색으로 하는 구현 문제

문제링크

코드

import java.io.*;
import java.util.StringTokenizer;

public class Baekjoon16986 {
    public static int n;
    public static int k;
    public static int[][] rule;
    public static int[] jiwoo;
    public static boolean[] usedHand;
    public static int[][] friends;
    public static int[] wins;
    public static int[] cursor;
    public static int result;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        rule = new int[n][n];
        jiwoo = new int[n];         //지우의 내는 순서
        usedHand = new boolean[n];  //내는 순서 탐색시 중복 확인
        friends = new int[2][20];   //경희, 민호 내는 순서
        wins = new int[3];          //우승 수 카운트
        cursor = new int[3];        //내는 순서 커서
        result = 0;                 //결과

        for(int i=0;i<n;i++) {  //규칙 입력
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++) {
                rule[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<20;i++)   //경희 내는 순서 입력
            friends[0][i] = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<20;i++)   //민호 내는 순서 입력
            friends[1][i] = Integer.parseInt(st.nextToken());
        
        dfs(0);
        bw.write(result+"");
        bw.flush();
    }

    public static void dfs(int d) {  //지우가 낼 수 있는 경우의 수 탐색
        if(d == n) { //끝까지 탐색했을 때
            wins = new int[3];
            cursor = new int[3];
            int r = game(0, 1);
            if(r == 0)
                result = 1;
        }
        else {  //끝까지 탐색 못했을 때
            for(int i=0;i<n;i++) {
                if(usedHand[i] == false) {
                    usedHand[i] = true;  //현재 사용하는 손동작 true로 변경
                    jiwoo[d] = i;
                    dfs(d+1);   //한층 더 탐색

                    usedHand[i] = false; //d+1 탐색 끝나면 false로 변경
                }
            }
        }
    }

    public static int game(int p1, int p2) {
        if(cursor[0]>=n)    //지우가 낼 수 있는 경우의 수 소진
            return -1;

        int win;
        if(p1 != 0 && p2 != 0)  //지우가 플레이어가 아닌 경우
            win = rule[friends[p1-1][cursor[p1]++]-1][friends[p2-1][cursor[p2]++]-1];
        else if(p1 == 0)        //첫번째 플레이어가 지우일 경우
            win = rule[jiwoo[cursor[p1]++]][friends[p2-1][cursor[p2]++]-1];
        else                    //두번째 플레이어가 지우일 경우
            win = rule[friends[p1-1][cursor[p1]++]-1][jiwoo[cursor[p2]++]];
        
        if(win == 2)        //p1의 승리
            win = p1;
        else if(win == 0)   //p2의 승리
            win = p2;
        else                //무승부일 경우 순서가 뒤인 사람 승리
            win = Math.max(p1, p2);
        wins[win]++;

        if(wins[win] == k)  //승수가 k에 도달하면 반환
            return win;
        
        return game(win, 3-p1-p2);
    }

}

해결 과정

코드짜는 것보다 문제 이해하는 것이 어려웠던 문제이다.

경기 진행 순서가 지우 → 경희 → 민호 순으로 정해져있는데 이것은 무승부일 때 아주 큰 영향을 준다.

침펄풍 예시에서는 무승부일 때 두번째 플레이어가 승리한다고 했지만

실제 문제에서는 경기 진행 순서가 뒤인 사람이 승리한다.

일단 지우의 내는 순서를 정해야 한다.

손동작은 최대 9개이고 손동작을 중복없이 나열하는 경우의 수를 구해서

게임을 시켜주면 된다.

손동작을 나열하는 경우의 수는 재귀방식의 깊이우선탐색으로 구현하였다.

public static void dfs(int d) {  //지우가 낼 수 있는 경우의 수 탐색
    if(d == n) { //끝까지 탐색했을 때
        wins = new int[3];
        cursor = new int[3];
        int r = game(0, 1);
        if(r == 0)
            result = 1;
    }
    else {  //끝까지 탐색 못했을 때
        for(int i=0;i<n;i++) {
            if(usedHand[i] == false) {
                usedHand[i] = true;  //현재 사용하는 손동작 true로 변경
                jiwoo[d] = i;
                dfs(d+1);   //한층 더 탐색

                usedHand[i] = false; //d+1 탐색 끝나면 false로 변경
            }
        }
    }
}

끝까지 탐색하면 게임을 시작한다.

public static int game(int p1, int p2) {
    if(cursor[0]>=n)    //지우가 낼 수 있는 경우의 수 소진
        return -1;

    int win;
    if(p1 != 0 && p2 != 0)  //지우가 플레이어가 아닌 경우
        win = rule[friends[p1-1][cursor[p1]++]-1][friends[p2-1][cursor[p2]++]-1];
    else if(p1 == 0)        //첫번째 플레이어가 지우일 경우
        win = rule[jiwoo[cursor[p1]++]][friends[p2-1][cursor[p2]++]-1];
    else                    //두번째 플레이어가 지우일 경우
        win = rule[friends[p1-1][cursor[p1]++]-1][jiwoo[cursor[p2]++]];
    
    if(win == 2)        //p1의 승리
        win = p1;
    else if(win == 0)   //p2의 승리
        win = p2;
    else                //무승부일 경우 순서가 뒤인 사람 승리
        win = Math.max(p1, p2);
    wins[win]++;

    if(wins[win] == k)  //승수가 k에 도달하면 반환
        return win;
    
    return game(win, 3-p1-p2);
}

이 함수도 재귀방식으로 게임을 풀어나가는데

종료조건은 2가지가 있다.

• 지우가 모든 손동작을 사용해버렸는데 경기가 남아있는 경우
• 한명이 승수를 채웠을 경우

그리고 결과가 지우의 승리가 나올 때 출력이 1 아니면 0이 된다.

결과