[LeetCode] 486. Predict the Winner - 게임이론(Game Theory) + 동적계획법(Dynamic Programming) + 깊이우선탐색(DFS) JAVA

https://leetcode.com/problems/predict-the-winner/description/

코드설명

게임이론(Game Theory) + 동적계획법(Dynamic Programming) + 깊이우선탐색(DFS) 을 활용합니다.

 

처음에는 완전탐색을 활용하여 해결하려했습니다만, 효율이 좋지 않습니다.

이유는, 게임이 20번 이기에 시간복잡도는 총 2^20 번 이기에 그렇습니다.

또한, 처음에 작성한 코드는 한계점이 존재합니다. 승패를 알 수는 있지만, 최대 몇점 차이로 이기는지는 알 수 없습니다.

 

자세한 풀이는 아래의 코드에 담았습니다.

코드

정답코드3입니다.

class Solution {
    int[] Nums;
    int[][] cache;
    public boolean predictTheWinner(int[] nums) {
        Nums = nums;
        cache = new int[nums.length][nums.length];
        for(int i=0; i<nums.length; i++)
            Arrays.fill(cache[i], Integer.MIN_VALUE);
        return game(0, nums.length - 1) >= 0;
    }

    //현재 Nums에 left, right일때 (이번 차례인 Player의 점수) - (다음 차례인 Player의 점수)의 최대치를 반환합니다.
    int game(int left, int right){
        if(left > right) return 0;
        if(cache[left][right] != Integer.MIN_VALUE) return cache[left][right];

        int ret = 0;
        int pickLeft = Nums[left] - game(left + 1, right);
        int pickRight = Nums[right] - game(left, right - 1);

        ret = Math.max(pickLeft, pickRight);
        return cache[left][right] = ret;
    }
}

 

게임이론(Game Theory)를 활용할경우입니다.

Player1의 입장에서는 최대 점수를 선택하고, Player2의 입장에서는 최소 점수를 선택합니다.

이때 원활하게 처리하기 위해 플레이어가 2명이므로 player1은 양수로 표현, player2는 음수로 표현하며 두 플레이어 간의 차이를 Player1은 최대화, Player2는 최소화 시킵니다(Player2는 음수가 본인의 점수이기에)

또한, 점수를 양수 음수로 표현하므로 Integer를 활용하여 null일 경우 무시합니다. 

이 방법의 단점은, left와 right만 가지고는 이번 차례가 누군지 알아낼 수 없기에 turn을 사용해야하고, 그 이유로, 부분 문제의 수가 두 배 늘어납니다.

class Solution {
    public boolean predictTheWinner(int[] nums) {
        int n = nums.length;
        Integer[][] memo = new Integer[n][n];
        return playGame(nums, 0, n - 1, 1, memo) >= 0;
    }

    private int playGame(int[] nums, int left, int right, int turn, Integer[][] memo) {
        if (left == right) {
            return nums[left] * turn;
        }

        if (memo[left][right] != null) {
            return memo[left][right];
        }

        int pickLeft = nums[left] * turn + playGame(nums, left + 1, right, -turn, memo);
        int pickRight = nums[right] * turn + playGame(nums, left, right - 1, -turn, memo);

        memo[left][right] = turn == 1 ? Math.max(pickLeft, pickRight) : Math.min(pickLeft, pickRight);
        return memo[left][right];
    }
}

 

아래의 틀린코드1을 고친 코드입니다. 문제점은, 모든 플레이어의 입장에서 처리하는 것이 아닌, 플레이어1이 이길 수 있냐 없냐만을 고려하며 그에 맞게 처리합니다. 

그렇기에 game() 함수를 isPlayer1Win으로 이름을 바꾸고, 아래와 같이 정의합니다.

isPlayer1Win() : Player1의 입장에서만 처리하며, Player1이 이긴다면 True를 반환하고, 진다면 False를 반환합니다.

이렇게 처리한 후, player1의 입장에서는 2가지 분기되는 재귀함수 중 한가지만 이김(true)를 반환하면 되고,

여기서 중요한점은, player2의 입장에서는 2가지 분기되는 재귀함수 중 두가지 모두 player1이 이겨야만 Player1이 이기는것이므로 && (AND) 연산으로 처리합니다. Player2 입장에서는 Player2가 이기는 선택을 할 것이기에, Player1 입장에서는 Player2의 턴에서도 모두 이겨야만 Player1이 이기는 것을 알 수 있습니다.

 

class Solution {
    int[] Nums;
    public boolean predictTheWinner(int[] nums) {
        Nums = nums;
        return isPlayer1Win(0, nums.length - 1, 0, 0, true);
    }
    //isPlayer1Win() : Player1의 입장에서만 처리하며, Player1이 이긴다면 True를 반환하고, 진다면 False를 반환합니다.
    boolean isPlayer1Win(int left, int right, int score1, int score2, boolean turn){
        if(left == right){
            if(turn == true) score1 += Nums[left];
            if(turn == false) score2 += Nums[left];
            //만약 score2가 더 크다면, score1 입장에서는 진것이고, score2입장에서는 이긴것이다.
            if(score1 < score2){
                return false;
            }
            //score2입장에서는 진것이므로.
            else if(score1 >= score2){
                return true;
            }
        }
        // if(left == right){ 더 좋은 방식입니다.
        //     return score1 >= score2;
        // }
        
        boolean ret = false;
        //player1 차례일때.
        //만약 한개라도 return true가 반환된다면 player1이 승리이므로 OR연산을 한다.
        if(turn == true){ 
            ret = false;
            ret |= isPlayer1Win(left + 1, right, score1 + Nums[left], score2, !turn);
            ret |= isPlayer1Win(left, right - 1, score1 + Nums[right], score2, !turn);
            return ret;
        } 
        //player2 입장에서는, 2개의 선택에서 player1이 한개라도 지는 경우(false)일 경우가 존재하면 
        //그 방안을 선택할 것이므로 둘 다 true가 나와야 player1이 이깁니다.
        else if(turn == false){
            ret = true;
            ret &= isPlayer1Win(left + 1, right, score1, score2 + Nums[left], !turn);
            ret &= isPlayer1Win(left, right - 1, score1, score2 + Nums[right], !turn);
            return ret;
        }
        return ret;
    }
}

 

처음에 틀린 코드1입니다. 무엇인가 놓친 것 같습니다.

class Solution {
    int[] Nums;
    public boolean predictTheWinner(int[] nums) {
        Nums = nums;
        return game(0, nums.length - 1, 0, 0, true);
    }

    boolean game(int left, int right, int score1, int score2, boolean turn){
        if(left == right){
            if(turn == true) score1 += Nums[left];
            if(turn == false) score2 += Nums[left];
            //만약 score2가 더 크다면, score1 입장에서는 진것이고, score2입장에서는 이긴것이다.
            if(score1 < score2){
                return !false;
            }
            //score2입장에서는 진것이므로.
            else if(score1 >= score2){
                return !true;
            }
        }

        //만약 한개라도 return true가 반환된다면 player1이 승리이므로 OR연산을 한다.
        boolean ret = false;
        //player1 차례일때.
        if(turn == true){ 
            ret |= game(left + 1, right, score1 + Nums[left], score2, !turn);
            ret |= game(left, right - 1, score1 + Nums[right], score2, !turn);
        } 
        //player2 입장에서도 
        else if(turn == false){
            ret |= game(left + 1, right, score1, score2 + Nums[left], !turn);
            ret |= game(left, right - 1, score1, score2 + Nums[right], !turn);
        }

        return ret;
    }
}