https://www.acmicpc.net/problem/16986
16986번: 인싸들의 가위바위보
두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주함에 다시 한 번 유의한다. 구체적으로, 경기 진행 순서는 지우, 경희, 민호 순으로 고정되
www.acmicpc.net
코드설명
Simulation(시뮬레이션) + Normal Permutation (일반순열) 을 활용하는 문제입니다.
코드로직을 간단하게 설명해보면 다음과 같습니다.
- getJiwooSelected: 지우가 선택할 수 있는 모든 경우의 수를 재귀적으로 조합하여 검사합니다.
- startGame: 게임을 시작하고, 조건에 따라 승자를 판단합니다.
- winCheck: 게임 결과에 따라 승자를 결정하고, 게임 인덱스를 업데이트합니다.
문제에서 주어진대로 구현하면 되는 문제입니다.
문제에서 제가 겪었던 유의해야할점들입니다.
1. 지우가 모든 가위바위보를 진행하려면 반드시 gameTurn은 N 보다 작거나 같아야만 N까지 갈 수 있습니다.
처음에 N까지 이동하지 않고, gameTurn < N 으로 처리하여 N의 길이가 아닌, N-1의 까지 계산하여 한가지를 빼먹어서 틀렸었습니다.
while(gameTurn <= N) { //처음에 < N 으로 처리하여서 N이 3이라면, selected는 3이 나오는데 이떄 selected를 2까지밖에 검사하지 않아서 틀렸었습니다.
2. 다음 플레이어 효율적으로 구하기
int nextPlayerCalculate = 3 - (nextPlayer0 + nextPlayer1);위의 코드를 통해 현재 선택되지 않은 플레이어의 Index를 바로 구할 수 있어, 많은 양의 코드가 획기적으로 줄었습니다.
이렇게 수학적인 계산방법은 인지하고 있어야만 합니다.
이러한 것들이 객체지향적으로 짜기 위해 필수적인 연산이라는 생각이 듭니다.
3. 문제에서 적절한 종료조건을 제시해야합니다.
예로 들었을떄 만약에 모든 가위바위보를 다 다르게 내면서 만약에 내기도 전에 이미 승리하는경우는?
아래와 같이 win==k일경우 바로 종료시킵니다.
또한 그러면서도, 지우가 이미 모두 다른 가위바위보를 냈는데도 불가할경우 종료시켜주어야합니다.
//이미 지우의 게임 플레이에는 모두 각각 다른 가위바위보가 들어가있습니다.
//그러므로 모든 승리가 완료된다면 이미 다른 각각의 가위바위보를 낸 것 입니다.
//또한 만약에 K가 0 일경우도 이를 통해 보완할 수 있습니다.
if(node[0].win == K) {
answer = 1;
return ;
}
//만약 지우가 모든 가위바위보를 내어놓고, 더이상 못낸다면 실패입니다.
if(node[0].playIndex == node[0].handArr.size()) {
// if(node[0].win == K) { //이 부분은 이미 앞에서 검증하여 제거해도 됩니다.
// answer = 1;
// return ;
// }else {
return ;
// }
}
4. 모든 연산 이후에는 원상복구를 해줌으로써, 이후의 함수 실행에 독립적으로 만들어줍니다.
연산이 진행된 후에 승리 수와 경기Index를 다시 원래대로 돌아오게 하여 다음의 실행에 영향을 주지 않도록 합니다.
else if(result == 0) {
player2.win += 1;
simulate(level + 1, player2.index, notparticipatePlayer);
player2.win -= 1;
}
//다음의 연산을 위한 원상복구가 필수적입니다.
player1.playIndex -= 1;
player2.playIndex -= 1;
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static int N,M,K;
public static int[][] map;
public static Node[] node = new Node[3]; //지우, 경희, 민호 순서입니다.
public static int answer = 0;
public static boolean flag = false;
public static boolean[] visited;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
visited = new boolean[N];
map = new int[N][N];
//2 일 경우에는 i번 손동작이 j번 손동작을 이긴다는 의미이다.
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i=0;i<3;i++) {
node[i] = new Node(i, 0, 0);
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<20;i++) {
node[1].handArr.add(Integer.parseInt(st.nextToken()) - 1) ;
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<20;i++) {
node[2].handArr.add(Integer.parseInt(st.nextToken()) - 1);
}
combination(0);
System.out.println(answer);
}
public static void combination(int level) {
if(level == N) {
// System.out.println("==============");
// for(int i=0;i<N;i++) {
// System.out.print(" "+node[0].handArr.get(i));
// }
// System.out.println();
if(answer == 0) {
simulate(0, 0, 1);
}
return ;
}
for(int i=0; i<N;i++) {
if(visited[i] == false) {
visited[i] = true;
node[0].handArr.add(i);
combination(level + 1);
node[0].handArr.remove(node[0].handArr.size() - 1);
visited[i] = false;
}
}
}
//경기 순서는 지우, 경희, 민호 순서이다.
public static void simulate(int level, int nextPlayer1, int nextPlayer2) {
//이미 지우의 게임 플레이에는 모두 각각 다른 플레이가 들어가있습니다.
if(node[0].win == K) {
answer = 1;
return ;
}
//만약 지우가 모든 플레이를 다 진행했다면,
if(node[0].playIndex == node[0].handArr.size()) {
// if(node[0].win == K) { //이 부분은 이미 앞에서 검증합니다.
// answer = 1;
// return ;
// }else {
return ;
// }
}
if(node[1].win == K || node[2].win == K) { //만약 다른사람이 이겼다면 종료시킵니다.
return ;
}
//(지우, 경희), (지우, 민호), (경희, 민호)
//다음 경기는 이긴사람과 참여안한사람이 경기합니다.
// System.out.println("nextPlayer1:"+nextPlayer1+" nextPlayer2:"+nextPlayer2);
Node player1 = node[nextPlayer1], player2 = node[nextPlayer2];
//지우가 참여하지 않는경우입니다.
//이제 가위바위보를 통해 누가 이길 것 인지 체크한다.
int hand1 = player1.handArr.get(player1.playIndex++);
int hand2 = player2.handArr.get(player2.playIndex++);
int result = map[hand1][hand2];
// System.out.println("result:"+result);
//player1이 이기는 경우입니다. player1과 아직 참여하지 않은 사람.
int notparticipatePlayer = 3 - ( player1.index + player2.index );
if(result == 2) {
player1.win += 1;
simulate(level + 1, player1.index, notparticipatePlayer);
player1.win -= 1;
}
//비길경우에는 진행순서상 뒤인 사람이 이긴것으로 간주한다.
//즉, index가 큰 사람이 이긴것으로 작동시킨다.
else if(result == 1) {
int drawPlayer = Math.max(player1.index, player2.index);
node[drawPlayer].win += 1;
simulate(level + 1, drawPlayer, notparticipatePlayer);
node[drawPlayer].win -= 1;
}
else if(result == 0) {
player2.win += 1;
simulate(level + 1, player2.index, notparticipatePlayer);
player2.win -= 1;
}
player1.playIndex -= 1;
player2.playIndex -= 1;
}
}
class Node{
int index;
int win;
int playIndex = 0;
ArrayList<Integer> handArr = new ArrayList<Integer>();
public Node(int index, int win, int playIndex) {
this.index = index;
this.win = win;
this.playIndex = playIndex;
}
}
객체지향적으로 접근해본 코드.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static int N,M,K;
public static int[][] map;
public static Node[] node = new Node[3]; //지우, 경희, 민호 순서입니다.
public static int answer = 0;
public static boolean flag = false;
public static boolean[] visited;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
visited = new boolean[N];
map = new int[N][N];
//2 일 경우에는 i번 손동작이 j번 손동작을 이긴다는 의미이다.
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i=0;i<3;i++) {
node[i] = new Node(i, 0, 0);
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<20;i++) {
node[1].handArr.add(Integer.parseInt(st.nextToken()) - 1) ;
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<20;i++) {
node[2].handArr.add(Integer.parseInt(st.nextToken()) - 1);
}
combination(0);
System.out.println(answer);
}
public static void combination(int level) {
if(level == N) {
if(answer == 0) {
simulate(0, 0, 1);
}
return ;
}
for(int i=0; i<N;i++) {
if(visited[i] == false) {
visited[i] = true;
node[0].handArr.add(i);
combination(level + 1);
node[0].handArr.remove(node[0].handArr.size() - 1);
visited[i] = false;
}
}
}
//경기 순서는 지우, 경희, 민호 순서이다.
public static void simulate(int level, int nextPlayer1, int nextPlayer2) {
//이미 지우의 게임 플레이에는 모두 각각 다른 가위바위보가 들어가있습니다.
//그러므로 모든 승리가 완료된다면 이미 다른 각각의 가위바위보를 낸 것 입니다.
//또한 만약에 K가 0 일경우도 이를 통해 보완할 수 있습니다.
if(node[0].win == K) {
answer = 1;
return ;
}
//만약 지우가 모든 가위바위보를 내어놓고, 더이상 못낸다면 실패입니다.
if(node[0].playIndex == node[0].handArr.size()) {
// if(node[0].win == K) { //이 부분은 이미 앞에서 검증하여 제거해도 됩니다.
// answer = 1;
// return ;
// }else {
return ;
// }
}
if(node[1].win == K || node[2].win == K) { //만약 다른사람이 이겼다면 종료시킵니다.
return ;
}
//(지우, 경희), (지우, 민호), (경희, 민호)
//다음 경기는 이긴사람과 참여안한사람이 경기합니다.
Node player1 = node[nextPlayer1], player2 = node[nextPlayer2];
//이제 가위바위보를 통해 누가 이길 것 인지 체크할 것 입니다.
int hand1 = player1.handArr.get(player1.playIndex++);
int hand2 = player2.handArr.get(player2.playIndex++);
int result = map[hand1][hand2];
//player1이 이기는 경우입니다. player1과 아직 참여하지 않은 사람.
int notparticipatePlayer = 3 - ( player1.index + player2.index );
if(result == 2) {
player1.win += 1;
simulate(level + 1, player1.index, notparticipatePlayer);
player1.win -= 1;
}
//비길경우에는 진행순서상 뒤인 사람이 이긴것으로 간주한다.
//즉, index가 큰 사람이 이긴것으로 작동시킨다.
else if(result == 1) {
int drawPlayer = Math.max(player1.index, player2.index);
node[drawPlayer].win += 1;
simulate(level + 1, drawPlayer, notparticipatePlayer);
node[drawPlayer].win -= 1;
}
else if(result == 0) {
player2.win += 1;
simulate(level + 1, player2.index, notparticipatePlayer);
player2.win -= 1;
}
//다음의 연산을 위한 원상복구가 필수적입니다.
player1.playIndex -= 1;
player2.playIndex -= 1;
}
}
class Node{
int index;
int win;
int playIndex = 0;
ArrayList<Integer> handArr = new ArrayList<Integer>();
public Node(int index, int win, int playIndex) {
this.index = index;
this.win = win;
this.playIndex = playIndex;
}
}
다음 플레이어를 3 - (nextPlayer0 + nextPlayer1) 을 통해 빠르게 구하여 코드양을 줄였습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K;
public static int[] arr;
public static int[][] A;
public static int[][] hand;
public static int[] selected;
public static boolean[] visited;
public static int answer = 0;
public static int jiwoo = 0, gyung = 1, minho = 2;
public static int nextPlayer0 = jiwoo, nextPlayer1 = gyung; //다음에 할 플레이어는 ?
public static int nextPlayerHand0 = 0;
public static int nextPlayerHand1 = 0;
public static int[] winCnt = new int[3]; //각 플레이어별로 몇번 이겼는가 ?
public static int[] gameIdx = new int[3]; // 각 플레이어의 게임횟수.
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
A = new int[N][N];
hand = new int[3][20];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
A[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i=1;i<3;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<20;j++) {
hand[i][j] = Integer.parseInt(st.nextToken()) - 1;
}
}
visited = new boolean[N];
selected = new int[N];
getJiwooSelected(0);
System.out.println(answer);
}
public static void getJiwooSelected(int level) {
if(level == N) {
//각 순서별로 이제 경기를 진행한다.
if( startGame() == true) {
answer = 1;
}
return ;
}
for(int i=0;i<N;i++) {
if(visited[i] == false) {
visited[i] = true;
hand[0][level] = i;
getJiwooSelected(level + 1);
visited[i] = false;
}
}
}
public static boolean startGame() {
winCnt = new int[3]; //각 플레이어별로 몇번 이겼는가 ?
gameIdx = new int[3]; // 각 플레이어의 게임횟수.
//게임 순서는 지우, 경희, 민호 순 입니다.
jiwoo = 0; gyung = 1; minho = 2;
nextPlayer0 = jiwoo; nextPlayer1 = gyung; //다음에 할 플레이어는 ?
nextPlayerHand0 = hand[nextPlayer0][gameIdx[nextPlayer0]];
nextPlayerHand1 = hand[nextPlayer1][gameIdx[nextPlayer1]];
int gameTurn = 0;
while(gameTurn <= N) { //처음에 < N 으로 처리하여서 N이 3이라면, selected는 3이 나오는데 이떄 selected를 2까지밖에 검사하지 않아서 틀렸었습니다.
gameTurn += 1;
nextPlayerHand0 = hand[nextPlayer0][gameIdx[nextPlayer0]];
nextPlayerHand1 = hand[nextPlayer1][gameIdx[nextPlayer1]];
//2 라면 nextPlayerHand0 가 nextPlayerHand1 을 이긴다는 의미입니다.
if(A[nextPlayerHand0][nextPlayerHand1] == 2) {
//nextPlayerHand1을 교체해줍니다.
winCheck(2);
}
//만약 1 이라면 경기순서가 더 뒤에있는 사람이 승리합니다.
else if(A[nextPlayerHand0][nextPlayerHand1] == 1) {
winCheck(1);
}
//만약 0 이라면, 진 것 입니다. nextPlayerHand0을 교체해줍니다.
else {
winCheck(0);
}
//만약 jiwoo의 승자횟수가 K라면 지우가 승리입니다.
if(winCnt[gyung] == K || winCnt[minho] == K)
return false;
if( winCnt[jiwoo] == K) {
return true;
}
}
//만약 jiwoo의 승자횟수가 K라면 지우가 승리입니다.
if(winCnt[gyung] == K || winCnt[minho] == K)
return false;
if( winCnt[jiwoo] == K) {
return true;
}
return false;
}
public static void winCheck(int type) {
gameIdx[nextPlayer0] += 1;
gameIdx[nextPlayer1] += 1;
int nextPlayerCalculate = 3 - (nextPlayer0 + nextPlayer1);
//nextPlayer0 가 이긴경우입니다.
if(type == 2) {
winCnt[nextPlayer0] += 1;
nextPlayer1 = nextPlayerCalculate;
}
//서로 비긴경우, 경기진행순서가 뒤인 사람이 이긴것으로 처리합니다.
else if(type == 1) {
//만약 nextPlayer0가 더 작다면, nextPlayer1 이 이긴 것 입니다.
if(nextPlayer0 < nextPlayer1) {
winCnt[nextPlayer1] += 1;
nextPlayer0 = nextPlayerCalculate;
}
//만약 nextPlayer0이 더 크다면, nextPlayer0 이 이긴 것 입니다.
else if(nextPlayer0 > nextPlayer1) {
winCnt[nextPlayer0] += 1;
nextPlayer1 = nextPlayerCalculate;
}
}
else if(type == 0) {
winCnt[nextPlayer1] += 1;
nextPlayer0 = nextPlayerCalculate;
}
}
}
처음에 푼 코드입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K;
public static int[] arr;
public static int[][] A;
public static int[][] hand;
public static int[] selected;
public static boolean[] visited;
public static int answer = 0;
public static int jiwoo = 0, gyung = 1, minho = 2;
public static int nextPlayer0 = jiwoo, nextPlayer1 = gyung; //다음에 할 플레이어는 ?
public static int nextPlayerHand0 = 0;
public static int nextPlayerHand1 = 0;
public static int[] winCnt = new int[3]; //각 플레이어별로 몇번 이겼는가 ?
public static int[] gameIdx = new int[3]; // 각 플레이어의 게임횟수.
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
A = new int[N][N];
hand = new int[3][20];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
A[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i=1;i<3;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<20;j++) {
hand[i][j] = Integer.parseInt(st.nextToken()) - 1;
}
}
visited = new boolean[N];
selected = new int[N];
getJiwooSelected(0);
System.out.println(answer);
}
public static void getJiwooSelected(int level) {
if(level == N) {
//각 순서별로 이제 경기를 진행한다.
if( startGame() == true) {
answer = 1;
}
return ;
}
for(int i=0;i<N;i++) {
if(visited[i] == false) {
visited[i] = true;
hand[0][level] = i;
getJiwooSelected(level + 1);
visited[i] = false;
}
}
}
public static boolean startGame() {
winCnt = new int[3]; //각 플레이어별로 몇번 이겼는가 ?
gameIdx = new int[3]; // 각 플레이어의 게임횟수.
//게임 순서는 지우, 경희, 민호 순 입니다.
jiwoo = 0; gyung = 1; minho = 2;
nextPlayer0 = jiwoo; nextPlayer1 = gyung; //다음에 할 플레이어는 ?
nextPlayerHand0 = hand[nextPlayer0][gameIdx[nextPlayer0]];
nextPlayerHand1 = hand[nextPlayer1][gameIdx[nextPlayer1]];
int gameTurn = 0;
while(gameTurn <= N) { //처음에 < N 으로 처리하여서 N이 3이라면, selected는 3이 나오는데 이떄 selected를 2까지밖에 검사하지 않아서 틀렸었습니다.
gameTurn += 1;
nextPlayerHand0 = hand[nextPlayer0][gameIdx[nextPlayer0]];
nextPlayerHand1 = hand[nextPlayer1][gameIdx[nextPlayer1]];
//2 라면 nextPlayerHand0 가 nextPlayerHand1 을 이긴다는 의미입니다.
if(A[nextPlayerHand0][nextPlayerHand1] == 2) {
//nextPlayerHand1을 교체해줍니다.
winCheck(2);
}
//만약 1 이라면 경기순서가 더 뒤에있는 사람이 승리합니다.
else if(A[nextPlayerHand0][nextPlayerHand1] == 1) {
winCheck(1);
}
//만약 0 이라면, 진 것 입니다. nextPlayerHand0을 교체해줍니다.
else {
winCheck(0);
}
//만약 jiwoo의 승자횟수가 K라면 지우가 승리입니다.
if(winCnt[gyung] == K || winCnt[minho] == K)
return false;
if( winCnt[jiwoo] == K) {
return true;
}
}
//만약 jiwoo의 승자횟수가 K라면 지우가 승리입니다.
if(winCnt[gyung] == K || winCnt[minho] == K)
return false;
if( winCnt[jiwoo] == K) {
return true;
}
return false;
}
public static void winCheck(int type) {
gameIdx[nextPlayer0] += 1;
gameIdx[nextPlayer1] += 1;
//nextPlayer0 가 이긴경우입니다.
if(type == 2) {
winCnt[nextPlayer0] += 1;
if( (nextPlayer0 == jiwoo && nextPlayer1 == gyung) || (nextPlayer0 == gyung && nextPlayer1 == jiwoo)) {
nextPlayer1 = minho;
}
else if( (nextPlayer0 == jiwoo && nextPlayer1 == minho) || (nextPlayer0 == minho && nextPlayer1 == jiwoo) ) {
nextPlayer1 = gyung;
}
else {
nextPlayer1 = jiwoo;
}
}
//서로 비긴경우, 경기진행순서가 뒤인 사람이 이긴것으로 처리합니다.
else if(type == 1) {
//만약 nextPlayer0가 더 작다면, nextPlayer1 이 이긴 것 입니다.
if(nextPlayer0 < nextPlayer1) {
winCnt[nextPlayer1] += 1;
if( (nextPlayer0 == jiwoo && nextPlayer1 == gyung) || (nextPlayer0 == gyung && nextPlayer1 == jiwoo)) {
nextPlayer0 = minho;
}
else if( (nextPlayer0 == jiwoo && nextPlayer1 == minho) || (nextPlayer0 == minho && nextPlayer1 == jiwoo) ) {
nextPlayer0 = gyung;
}
else {
nextPlayer0 = jiwoo;
}
}
//만약 nextPlayer0이 더 크다면, nextPlayer0 이 이긴 것 입니다.
else if(nextPlayer0 > nextPlayer1) {
winCnt[nextPlayer0] += 1;
if( (nextPlayer0 == jiwoo && nextPlayer1 == gyung) || (nextPlayer0 == gyung && nextPlayer1 == jiwoo)) {
nextPlayer1 = minho;
}
else if( (nextPlayer0 == jiwoo && nextPlayer1 == minho) || (nextPlayer0 == minho && nextPlayer1 == jiwoo) ) {
nextPlayer1 = gyung;
}
else {
nextPlayer1 = jiwoo;
}
}
}
else if(type == 0) {
winCnt[nextPlayer1] += 1;
if( (nextPlayer0 == jiwoo && nextPlayer1 == gyung) || (nextPlayer0 == gyung && nextPlayer1 == jiwoo)) {
nextPlayer0 = minho;
}
else if( (nextPlayer0 == jiwoo && nextPlayer1 == minho) || (nextPlayer0 == minho && nextPlayer1 == jiwoo) ) {
nextPlayer0 = gyung;
}
else {
nextPlayer0 = jiwoo;
}
}
}
}