[BOJ 16986] 인싸들의 가위바위보 (Java)

BOJ 16986 인싸들의 가위바위보

문제풀이

첨부그림 때문에 문제를 풀 의욕이 없어지는 문제, 하지만 알고보면 평소에 풀던 완전탐색과 다를 바가 없다.

1. 지우가 낼 수 있는 N개의 손동작을 순열로 구한다.
2. 지우, 경희, 민호의 게임을 시뮬레이션 한다.

• 승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주한다.라는 말은 두 번째 참가자가 무조건 이기는 것이 아니라 지우, 경희, 민호의 순서에서 뒤쪽에 있는 사람이 이긴다는 뜻이다.
• 이 문제에서 지우는 서로다른 손동작을 내야하기 때문에 N번의 경기안에 승점을 채우지 못하면 실패한 것이다. 해당 조건을 위해서는 전체 경기의 수가 N번이 아니라 지우가 참가한 경기가 N번 이하여야한다는 조건이 필요하다.
• DFS 구현시 일반적으로 탈출조건을 depth를 한 번 더 들어간 후에 확인하기 때문에 이에 주의하여 조건을 정하고 조건 간의 순서도 생각해야한다.

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int[][] map;
	static int[][] hands;
	static int[] handIdx;
	static int[] winCnt;
	static boolean[] visited;
	static boolean isWin;
	static int N, K;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
	
		N = stoi(st.nextToken());
		K = stoi(st.nextToken());
		
		// 낼 수 있는 손동작 수 보다 승수가 더 클 때 
		if(N < K) {
			System.out.println(0);
			return;
		}
		
		map = new int[N + 1][N + 1];
		hands = new int[3 + 1][20];
		visited = new boolean[N + 1];
		
		// 상성표 입력 
		for(int i = 1 ; i <= N ; ++i) {
			st = new StringTokenizer(br.readLine());
			for(int j = 1 ; j <= N ; ++j) {
				map[i][j] = stoi(st.nextToken());
			}
		}
		
		// 경희 손동작 입력 
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < 20 ; ++i) hands[2][i] = stoi(st.nextToken());
		// 민호 손동작 입력 
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < 20 ; ++i) hands[3][i] = stoi(st.nextToken());
		// 지우 손동작 순열 
		permutation(0);
		
		if(isWin) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
	}
	
	private static void permutation(int times) {
		if(isWin) return;
		
		if(times == N) {
			isWin = false;
			handIdx = new int[4];
			winCnt = new int[4];
			
			// 시뮬레이션 시작
			if(simulation(1, 2)) {
				isWin = true;
			};
			
			return;
		}
		
		for(int i = 1 ; i <= N ; ++i) {
			if(!visited[i]) {
				visited[i] = true;
				hands[1][times] = i;
				
				permutation(times + 1);
				if(isWin) return;
				
				hands[1][times] = 0;
				visited[i] = false;
			}
		}
	}

	private static boolean simulation(int P1, int P2) {
    		// Idx가 N이상인지 확인하는 것 보다 먼저 해야함 
    		if(winCnt[1] >= K) {
                    return true;
             	}
        
		if(handIdx[1] >= N || winCnt[2] >= K || winCnt[3] >= K) {
			return false;
		}
		
		int nextPlayer;
		// 다음 게임의 플레이어 찾기 (현재 게임에 참여하지 않는 사람)
		if((P1 == 1 && P2 == 2) || (P1 == 2 && P2 == 1)) nextPlayer = 3;
		else if((P1 == 1 && P2 == 3) || (P1 == 3 && P2 == 1)) nextPlayer = 2;
		else nextPlayer = 1;
		
		// 현재 게임의 결과 
		int result = map[hands[P1][handIdx[P1]]][hands[P2][handIdx[P2]]];
		// 게임 참가자들의 손동작 인덱스 +1 
		handIdx[P1]++;
		handIdx[P2]++;
		
		// 플레이어1 승리 
		if(result == 2) {
			winCnt[P1]++;
			if(simulation(P1, nextPlayer)) return true;
		// 플레이어2 승리 
		} else if(result == 0) {
			winCnt[P2]++;
			if(simulation(P2, nextPlayer)) return true;
		// 무승부 
		} else {
			// 게임 순서에서 뒤쪽인 사람이 승리 (숫자가 큰 사람) 
			// 지우 > 경희 > 민호
			if(P1 > P2) {
				winCnt[P1]++;
				if(simulation(P1, nextPlayer)) return true;
			} else {
				winCnt[P2]++;
				if(simulation(P2, nextPlayer)) return true;
			}
		}
		
		return false;
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}