인싸들의 가위바위보 [백준 16986][순열][DFS]

 

[광고 누르면 오늘의 행운 상승!!]

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

16986번: 인싸들의 가위바위보

문제 설명이 더러운 문제
이해가 너무 너무 안되서 블로그를 참고했다.

1. 참고사항
- 이긴사람이 다음 경기에 출전
- 비기면 지우 < 경희 < 민호 순으로 승리
- 경희와 민호의 순서는 자기차례마다 돌아간다. 

2. 구현

- 지우의 손동작 N개의 순열을 구해서 지우가 낼 손동작의 순서를 뽑는다.
- 지우와 경희를 시작으로 가위바위보 DFS를 시작한다.
- 지우의 승수가 K보다 크거나 같다면 return
- 지우가 낸 손동작 수가 N보다 크거나 같거나, 경희 or 민호의 승수가 K 보다 크다면 return
- 인수로 player1, player2를 받아 도전자 player3을 구한다.
- 현재 게임의 결과를 상성표를 이용하여 구하여 handIdx[사람]의 숫자를 ++한다.
- 이긴사람을 정해 dfs를 돌린다.
- 무승부라면 지우 < 경희 < 민호 순으로 승리한다.
- 반복하여 return true가 나올 때까지 구한다. 

종료.

package Study9;

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

public class 인싸들의가위바위보 {
	
	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 {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
	
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(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] = Integer.parseInt(st.nextToken());
			}
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < 20 ; ++i) hands[2][i] = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < 20 ; ++i) hands[3][i] = Integer.parseInt(st.nextToken());

		permutation(0);
		
		if(isWin) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
	}
	
	private static void permutation(int cnt) {
		if(isWin) return;
		
		if(cnt == N) {
			isWin = false;
			handIdx = new int[4];
			winCnt = new int[4];
			
			// 시뮬레이션 시작
			if(dfs(1, 2)) {
				isWin = true;
			};
			
			return;
		}
		
		for(int i = 1 ; i <= N ; ++i) {
			if(!visited[i]) {
				visited[i] = true;
				hands[1][cnt] = i;
				
				permutation(cnt + 1);
				if(isWin) return;
				
				hands[1][cnt] = 0;
				visited[i] = false;
			}
		}
	}

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

3. 참고 블로그

https://velog.io/@hyeon930/BOJ-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-Java

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