[프로그래머스/C++] 사라지는 발판

 

 

문제

SWEA 문제

 

[문제 설명]

​

밟고 지나가면 사라지는 발판이 있다. A 플레이어와 B 플레이어가 번갈아 가면서 게임을 하고, 각자 최선의 플레이를 한다.

 

만약 A가 무조건 이기게 된다면 B는 최대한 발판을 오래 밟아야 하고, A 는 최대한 게임을 빨리 끝내도록 플레이 한다.

 

B가 무조건 이기게 되는 경우도 마찬가지로 B는 최대한 빨리 게임을 끝내고 A는 최대한 발판을 오래 밟으면 된다.

 

이 때, 게임이 진행되는 횟수를 구하면 되는 문제다.

 

 

 

풀이

 

[풀이]

 

이 문제는 제한사항이 작기 때문에, 시간을 크게 고려하지 않아도 되는 문제다.

 

중요한 점은 항상 두 플레이어가 최선의 수를 둔다는 점인데, 어떤 플레이어가 이길지 모르기 때문에 조건을 잘 설정하는 것이 중요하다.

 

만약 A 플레이어가 무조건 이기는 수가 있다면, A플레이어는 그 수를 써서 가장 빠르게 이기도록 하면 되고, B 플레이어는 최대한 발판을 많이 밟는 경우를 return하면 된다.

 

반대로 B 플레이어가 무조건 이기는 수가 있다면, A 플레이어는 최대한 많은 발판을 밟는 경우로 수를 두어야 하고, B 플레이어는 최대한 빨리 이기도록 수를 두면 된다.

 

아이디어 자체는 어렵지 않은데, 구현하는데 생각보다 시간이 오래걸렸다.

 

[풀이 요약]

 

1. 현재 상황에서 플레이 할 경우 누가 이기는 경우인지 구한다.
2. 내가 이기는 경우 최대한 빨리 게임을 끝내는 횟수를 return한다.
3. 만약 내가 지는 경우 최대한 오래 게임을 진행하는 횟수를 return한다.
4. 위 과정을 재귀적으로 반복한다.

 

 

 

Code

 

 

#include <string>
#include <vector>
using namespace std;

vector<vector<int>> realBoard;
int YSize;
int XSize;
int dy[4]={1, -1, 0, 0};
int dx[4]={0, 0, 1, -1};

// pair<bool,int> A가 이기는 경우 pair.first=true, int는 최소
pair<bool,int> AWinFunc(vector<int>nowA, vector<int>nowB, bool aTurn, int nowCnt)
{   // A를 기준으로 판단을 한다.    
    pair<bool,int> returnP=make_pair(false,nowCnt);
    pair<bool,int> nowP;
    int nx,ny;   
    bool flag=false;
    vector<int> ToV(2);
    if (aTurn)
    {
        for (int i=0; i<4; i++)
        {
            ny=nowA[0]+dy[i];
            nx=nowA[1]+dx[i];
            if (0<=ny&&ny<YSize&&0<=nx&&nx<XSize && realBoard[ny][nx]==1)
            {
                if (nowA==nowB)
                {   // A가 이동해서 이기는 상황
                    returnP.first=aTurn;
                    returnP.second+=1;
                    return returnP;
                }
                ToV[0]=ny;
                ToV[1]=nx;
                realBoard[nowA[0]][nowA[1]]=0;
                nowP=AWinFunc(ToV,nowB,!aTurn,nowCnt+1);
                if (nowP.first)
                {
                    // 무조건 자기가 유리한 경우 이므로 이때의 returnP를 nowP로 바꿔준다
                    if (!flag)
                    {
                        flag=true;
                        returnP.second=nowP.second;
                    }                    
                    else
                    {
                        if (returnP.second>nowP.second)
                        {
                            returnP.second=nowP.second;
                        }
                    }
                }                
                if(!flag)
                {
                    // 자기가 지는 경우이므로 가장 긴 second로 바꿔주면 된다.
                    if (returnP.second<nowP.second)
                    {
                        returnP.second=nowP.second;
                    }
                }
                realBoard[nowA[0]][nowA[1]]=1;
            }
        }
        returnP.first=flag;
        return returnP;
    }
    else
    {
        for (int i=0; i<4; i++)
        {
            ny=nowB[0]+dy[i];
            nx=nowB[1]+dx[i];
            if (0<=ny&&ny<YSize&&0<=nx&&nx<XSize && realBoard[ny][nx]==1)
            {
                if (nowA==nowB)
                {
                    returnP.first=aTurn;
                    returnP.second+=1;              
                    return returnP;
                }
                ToV[0]=ny;
                ToV[1]=nx;
                realBoard[nowB[0]][nowB[1]]=0;
                nowP=AWinFunc(nowA,ToV,!aTurn,nowCnt+1);
                if (!nowP.first)
                {
                    if (!flag)
                    {
                        flag=true;
                        returnP.second=nowP.second;
                    }                    
                    else
                    {
                        if (returnP.second>nowP.second)
                        {
                            returnP.second=nowP.second;
                        }
                    }                    
                    
                }
                if(!flag)
                {
                    // 자기가 지는 경우이므로 가장 긴 second로 바꿔주면 된다.
                    if (returnP.second<nowP.second)
                    {
                        returnP.second=nowP.second;
                    }                    
                }  
                realBoard[nowB[0]][nowB[1]]=1;                
            }
        }
        returnP.first=!flag;
        return returnP;
    }
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    // 무조건 이기는 수가 있는지 체크하는 함수 => 무조건 이기는 사람이 누군지 알려주는 함수다.
    // 결정이 나면, 그때의 횟수를 return하면 된다.
    realBoard=board;
    YSize=board.size();
    XSize=board[0].size();
    pair<bool,int> ttanswer = AWinFunc(aloc,bloc,true,0);
    return ttanswer.second;
}

 

---

 

처음에 코드를 작성할 때, 최선의 수를 둘 경우 누가 무조건 이기는지를 구하도록 작성했다.

 

이후 결과 값을 바탕으로 최선의 수를 두도록 코드를 짜려고 했더니, 반복되는 코드가 생기게 돼 하나의 함수로 누가 승리하는지와 횟수를 return하도록 코드를 짰다...

 

문제는 작성된 코드를 바꾸다 보니까 변수가 헷갈려 버렸고, 심지어 코드 줄을 잘못 작성해 헤매버렸다...

진짜 뜬금없이 시간이 오래걸려버리네;;

 

A와 B 경우 둘다 나눴더니 코드도 길어졌는데 코드 길이를 줄이려면 어떻게 하는게 좋을까...

 

프로그래머스