사라지는 발판 [Lv. 3]

프로그래머스

1x1 크기 정사각 격자로 이루어진 게임 보드 위에 두 플레이어가 있습니다.

플레이어는 위, 아래, 좌, 우로 움직일 수 있으며 움직이면 원래 위치의 발판이 사라지게됩니다.

패배 조건은 이동할 곳이 없거나, 현재 위치한 발판이 사라지는 경우입니다.

이때 두 플레이어가 최선을 다해서 게임을 할 때 두 플레이어의 이동 횟수의 합을 구하는 문제입니다. 

 

풀이 방법

게임 보드의 크기가 최대 5 * 5로 굉장히 작은 크기에 속합니다.

따라서 DFS로 모든 경로에 대한 탐색을 해보는 것이 좋을 듯 합니다.

 

내가 지는 경우와 이기는 경우로 나누어서 플레이 방식을 구분해야합니다.

지는 경우는 최대한 오래 살 수 있도록 도망가야하며

이기는 경우는 최대한 빨리 끝내도록 해야합니다.

 

이기고 지는 것의 구분은 DFS 함수의 return 값으로 하였습니다.

int DFS(vector<vector<int>>& board, int y, int x, int oy, int ox)
...
...
...
    for(int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        if (!Check(board, ny, nx))
            continue;
        
        // return 값이 0이면 진거
        int value = DFS(board, oy, ox, ny, nx) + 1;

내가 움직인 이후의 DFS는 상대방의 관점에서 시작되며

갈곳이 없거나 내가 위치한 발판이 사라졌을 때는 0을 반환하는데

반환값을 받을 때 1을 더해주고 있습니다.

 

즉 (상대방의 관점에서 시작한 함수의 반환값 + 1) % 2가 0이라면 나의 패배 1이면 나의 승리입니다.

// 패배였는데 이기는 경우가 있다면
if (cnt % 2 == 0 && value % 2 == 1)
    cnt = value;

// 무조건 진다면 ? 최대한 도망
else if (cnt % 2 == 0 && value % 2 == 0)
    cnt = max(cnt, value);

// 무조건 승리 ? 최대한 빠르게
else if (cnt % 2 == 1 && value % 2 == 1)   
    cnt = min(cnt, value);

이후 상황에 맞게 무조건 진다면 멀리 이동하는 쪽으로 선택

무조건 이긴다면 조금 이동하는 쪽으로 선택합니다.

(이기는 경우가 있는데 패배하는 경우가 나오면 생략합니다)

 

그럼 최종적으로 승패 결과에 따른 최적의 이동횟수가 반환됩니다.

 

정답 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int Check(vector<vector<int>>& board, int y, int x)
{
    return y >= 0 && y < board.size() && x >= 0 && x < board[0].size() && board[y][x] == 1;
}

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int DFS(vector<vector<int>>& board, int y, int x, int oy, int ox)
{
    if (board[y][x] == 0){
        return 0;
    }
    
    int cnt = 0;
    
    board[y][x] = 0;
    
    for(int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        if (!Check(board, ny, nx))
            continue;
        
        // return 값이 0이면 진거
        int value = DFS(board, oy, ox, ny, nx) + 1;
        
        // 패배였는데 이기는 경우가 있다면
        if (cnt % 2 == 0 && value % 2 == 1)
            cnt = value;
        
        // 무조건 진다면 ? 최대한 도망
        else if (cnt % 2 == 0 && value % 2 == 0)
            cnt = max(cnt, value);
        
        // 무조건 승리 ? 최대한 빠르게
        else if (cnt % 2 == 1 && value % 2 == 1)   
            cnt = min(cnt, value);
    }
    
    board[y][x] = 1;
    return cnt;
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    return DFS(board, aloc[0], aloc[1], bloc[0], bloc[1]);
}