백준_인싸들의 가위바위보[Java]

문제 

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

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

dfs를 사용하면 되는 문제다.

dfs문제의 높은 난이도 문제같다. 왕어렵다.

---

풀이

import java.util.Scanner;

public class Main {
	static int N, M; // N : 손가락 가지수, M : 목표 승수
	static int pick[][];  // 각 플레이어의 차례별로 낼 모양을 저장한 배열 
	static int arr[][];  // 각 손가락 모양별 상성을 저장할 배열 
	private static boolean result = false;

	public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        
        pick = new int[3][21];  // 3명의 사람의 20경기 정보를 가짐
        arr = new int[12][12];   // 낼 수 있는 손동작의 수를 12개로 본것 같음 
        for(int i = 1; i <= N; i++) {
        		for(int j = 1; j <= N; j++) {
        			arr[i][j] = sc.nextInt();
        		}
        }
        
        for(int i = 0; i < 20; i++) { // 경희
        	 	pick[1][i] = sc.nextInt();
        }
        
        for(int i = 0; i < 20; i++) { // 민호 
	    	 	pick[2][i] = sc.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);
        
        sc.close();
    }

	// dfs 깊이우선탐색 
	private static void solution(int user1, int user2, int[] winCount, int[] turnCount, boolean[] used) {
		// user1과 user2는 각각 유저번호를 의미
		// winCount 는 해당 상태에서 각 플레이어의 승수 
		// winCount[0] : 지우의 승수, winCount[1] : 경희의 승수 , winCount[2] : 민호의 승수 
		// turnCount 는 해당 상황에서 각 플레이어가 몇번째 차례를 맞이했는지
		// turnCount[0] : 지우의 차례순서, turnCount[1] : 경희의 차례순서 , turnCount[2] : 민호의 차례순서
		// userd는 모든 손가락 가지수에 대해 지우가 사용했는지 안했는지를 저장
		
		if(winCount[0] == M) { // 지우가 먼저 목표 승수에 도달 
			result = true;
			return; // wow 
		}
		
		else if(winCount[1] == M | winCount[2] == M) {
			return;
		}
		
		int userNext = 3-user1-user2;
		// 이번 게임이 끝나고 다음 상대로 만날 사람을 저장
		// 지우 : 0  , 경희 : 1 , 민호 : 2
		
		if(user1 == 0) { // user1이 지우라면 
			for(int i = 1; i <= N; i++) {
				if(!used[i]) { // 사용하지 않은 손가락
					int winner = rsp(i, pick[user2][turnCount[user2]], 0, user2);
					winCount[winner]++;
					turnCount[user2]++;
					used[i] = true;
					// 냈다는 가정하에 다음 경기 진행이라고 함 
					solution(winner, userNext, winCount, turnCount, used); 
					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);
			// 이 함수도 끝에 도달하면 돌아오기 때문에 아래와 같이 원상태로 돌려줘야 한다. 
			winCount[winner]--;
			turnCount[user1]--;
			turnCount[user2]--;
		}
	}

	// 승자 리턴 함수
	private static int rsp(int pick1, int pick2, int user1, int user2) {
		// pick1 : user1의 손가락 번호 
		// pick2 : user2의 손가락 번호 
		// k : user1 의 번호 (지우)
		
		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;
	}

}

---

흐름 

- main 메소드

1. arr[][]에 모든 상성을 다 넣어둔다. (번호 별 승부 내용)

2. pick에 경희와 민호가 낼 손가락 번호를 순서대로 넣는다. 

 

- solution 메소드 

3. solution 메소드를 이용해 지우가 winner인 경우를 dfs로 찾는다.

지우가 winner인 경우가 발생하면 result를 true로

그런 경우가 발생하지 않으면 false를 반환하게 만든다. 

4. dfs를 사용하는 이유는 경기 끝까지 진행해 지우가 winner인 경우를 찾아야하기 때문이다.

5. 지우 혹은 경희/민호가 이기면 return 한다. 

6. 다음 경기를 진행할 상대를 userNext 변수에 저장해둔다.

     userNext = 3-user1-user2;

7. 참고 블로그에서 지우가 경기에 참여하는 경우와 그렇지 않은 경우로 나눠서 풀으셔서 따라했다.

    user1과 user2를 정렬한다면 지우가 참여했을 경우에 무조건 user1이 지우이기 때문에 조건식이 하나 줄어든다.

    하지만 나는 정렬하지 않고 그대로 user1을 확인하거나 user2를 확인했다. 이것도 따라한 것,,, 

8. 지우가 사용한 손가락 모양은 다시 사용하면 안되게 때문에 used[] 배열을 통해 사용한 손가락 모양을 저장해뒀다. 

   사용하지 않은 손가락 모양만 사용한다 if(!used[i])

9. rsp 메소드를 이용해 해당 순서 게임의 승자를 구한 후 winner에 저장한다. 

10. 이긴 사람 (winner)의 이긴 승수를 올리고, 각 user1과 user2의 차례도 올린 후 (해당 차례의) 승부가 났다는 가정하에 

     solution 메소드를 호출하여 (이 때 user1은 winner로 user2는 다음 상대인 userNext로 보내준다.)

     다음 승부를 가린다. ------> dfs

11. 전체적인 승부가 났을 경우 지우가 이겨서 result값이 true이 되었을 수도 있지만 이번 경우에서는 이기지 못해 false를 반환할 수도 있다.

    따라서 다음 경우의 수를 확인하기 위해 모든 상태를 원상복귀 시킨다. 

 

- rsp 메소드

user1과 user2가 해당 순서에 낸 손가락 모양 번호(각각 pick[user][turnCount[user]] 이거나 지우인 경우 현재 전해진 손가락 모양 번호)를 가져와서 arr[][] 배열에 저장된 승부표를 확인한다.

2인 경우 user1이 user2를 이긴 것이고  return user1;

0인 경우 user2가 user1을 이긴 것이다.  return user2;

그런데 이때 손가락 번호가 같아 비겼을 경우 뒷 순서의 user가 이겼기 때문에 뒷사람 번호를 반환해준다. return Math.max(user1, user2);

 

 

 

---

 

* 궁금한 점 : 중간에 result의 값이 true가 되었을 경우에는 다른 경우의 수를 확인할 필요가 없지 않은가 ? 

                    그렇다면 result값이 true가 되었을 때 아예 모든 solution함수에서 벗어나면 어떠할까 ?

 

---

 

참고

이분거를 거의 다,.. 참고했다고 보면 된댜. 감삼다 !!!

https://algwang.tistory.com/62?category=1026348

16986. 인싸들의 가위바위보