코딩테스트 -- 사라지는 발판 - (프로그래머스 / C++)

프로그래머스

 

문제!

---

플레이어 A와 플레이어 B가 서로 게임을 합니다. 당신은 이 게임이 끝날 때까지 양 플레이어가 캐릭터를 몇 번 움직이게 될지 예측하려고 합니다.

각 플레이어는 자신의 캐릭터 하나를 보드 위에 올려놓고 게임을 시작합니다. 게임 보드는 1x1 크기 정사각 격자로 이루어져 있으며, 보드 안에는 발판이 있는 부분과 없는 부분이 있습니다. 발판이 있는 곳에만 캐릭터가 서있을 수 있으며, 처음 캐릭터를 올려놓는 곳은 항상 발판이 있는 곳입니다. 캐릭터는 발판이 있는 곳으로만 이동할 수 있으며, 보드 밖으로 이동할 수 없습니다. 밟고 있던 발판은 그 위에 있던 캐릭터가 다른 곳으로 이동하여 다른 발판을 밞음과 동시에 사라집니다. 양 플레이어는 번갈아가며 자기 차례에 자신의 캐릭터를 상하좌우로 인접한 4개의 칸 중에서 발판이 있는 칸으로 옮겨야 합니다.

다음과 같은 2가지 상황에서 패자와 승자가 정해지며, 게임이 종료됩니다.

• 움직일 차례인데 캐릭터의 상하좌우 주변 4칸이 모두 발판이 없거나 보드 밖이라서 이동할 수 없는 경우, 해당 차례 플레이어는 패배합니다.
• 두 캐릭터가 같은 발판 위에 있을 때, 상대 플레이어의 캐릭터가 다른 발판으로 이동하여 자신의 캐릭터가 서있던 발판이 사라지게 되면 패배합니다.

게임은 항상 플레이어 A가 먼저 시작합니다. 양 플레이어는 최적의 플레이를 합니다. 즉, 이길 수 있는 플레이어는 최대한 빨리 승리하도록 플레이하고, 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이합니다. '이길 수 있는 플레이어'는 실수만 하지 않는다면 항상 이기는 플레이어를 의미하며, '질 수밖에 없는 플레이어'는 최선을 다해도 상대가 실수하지 않으면 항상 질 수밖에 없는 플레이어를 의미합니다. 최대한 오래 버틴다는 것은 양 플레이어가 캐릭터를 움직이는 횟수를 최대화한다는 것을 의미합니다.

아래 그림은 초기 보드의 상태와 각 플레이어의 위치를 나타내는 예시입니다.

 

제한사항

• 1 ≤ board의 세로 길이 ≤ 5
• 1 ≤ board의 가로 길이 ≤ 5
• board의 원소는 0 또는 1입니다.
  • 0은 발판이 없음을, 1은 발판이 있음을 나타냅니다.
  • 게임 보드의 좌측 상단 좌표는 (0, 0), 우측 하단 좌표는 (board의 세로 길이 - 1, board의 가로 길이 - 1)입니다.
• aloc과 bloc은 각각 플레이어 A의 캐릭터와 플레이어 B의 캐릭터 초기 위치를 나타내는 좌표값이며 [r, c] 형태입니다.
  • r은 몇 번째 행인지를 나타냅니다.
  • 0 ≤ r < board의 세로 길이
  • c는 몇 번째 열인지를 나타냅니다.
  • 0 ≤ c < board의 가로 길이
  • 초기 보드의 aloc과 bloc 위치는 항상 발판이 있는 곳입니다.
  • aloc과 bloc이 같을 수 있습니다.
• 상대 플레이어의 캐릭터가 있는 칸으로 이동할 수 있습니다.

---

문제를 요약해보면

2명의 플레이어가 사각 틀을 한칸씩 이동해 나가면서 더이상 이동할수가 없는 플레이어가 지는 경우의 단순 게임에서 

최소의 A플레이어 움직임 + B플레이어 움직임 횟수를 구하는 문제입니다!

 

 

승부를 결정지을수있는 움직임의 최소횟수.... 이때까지 풀어온 문제를 보면 dp 누적합 무슨 알고리즘 등등 많긴한데..

 

완전 탐색 밖에 생각나질않네요

물론 탐색 범위가 수없이 많으면 완전탐색은 시간초과가 나겠지만

보드의 길이가 5! 총 칸이 25칸 밖에 되지않는다는점에서  완전탐색을 통해 풀어 보겠습니다.

 

 

첫번째 실패코드;;

#include <string>
#include <vector>

#include <iostream>

using namespace std;

int dy[] = {-1,1,0,0};//상 하 좌 우
int dx[] = {0,0,-1,1};

int answer = 987654321;

void find(vector<vector<int>> board,vector<int> P1,vector<int> P2, int Who_P,int count){

    int max_y=board.size();
    int max_x=board[0].size();
    vector<int> memo;
    bool move=false;
    
    if(board[P1[0]][P1[1]]==0 or board[P2[0]][P2[1]]==0){
        answer=min(answer,count);
    }

    for(int i=0;i<4;i++){
        if(Who_P==0){//P1 움직일 순서
            if((max_y>P1[0]+dy[i] and P1[0]+dy[i]>=0) and(max_x>P1[1]+dx[i] and P1[1]+dx[i]>=0)){
                if(P2[0]==P1[0]+dy[i] and P2[1] == P1[1]+dx[i]){// 그칸에 이미 누가 있다면? 일단 피하기
                    memo=P2;
                }
                else if(board[P1[0]+dy[i]][P1[1]+dx[i]]==1){// 그 칸이 비어있는지
                    board[P1[0]][P1[1]]=0;// 지나간칸 처리
                    find(board,{P1[0]+dy[i],P1[1]+dx[i]},P2,1,count+1);
                    move=true;
                    //board[P1[0]][P1[1]]=1;
                }
            }
            
        }
        else{
            if((max_y>P2[0]+dy[i] and P2[0]+dy[i]>=0) and(max_x>P2[1]+dx[i] and P2[1]+dx[i]>=0)){
                if(P1[0]==P2[0]+dy[i] and P1[1] == P2[1]+dx[i]){// 그칸에 이미 누가 있다면? 일단 피하기
                    memo=P1;
                }
                else if(board[P2[0]+dy[i]][P2[1]+dx[i]]==1){// 그 칸이 비어있는지
                    
                    board[P2[0]][P2[1]]=0;// 지나간칸 처리
                    find(board,P1,{P2[0]+dy[i],P2[1]+dx[i]},0,count+1);
                    move=true;
                    //board[P2[0]][P2[1]]=1;
                }
            }
        }
    }
    
    if(not move){
        if(memo.size()){
            if(Who_P==0){
                board[P1[0]][P1[1]]=0;// 지나간칸 처리
                find(board,memo,P2,1,count+1);
            }
            else{
                board[P2[0]][P2[1]]=0;// 지나간칸 처리
                find(board,P1,memo,0,count+1);
            }
        }
        else{
            answer=min(answer,count);
        }
    }     
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    find(board,aloc,bloc,0,0);
    return answer;
}

 

위의 코드는 완전탐색중에 플레이어 끼리 같은칸에 있는걸 약간 피해주고 이동시키는 코드입니다.....

 

위처럼 코드를 작성하고나서 실패가 떠서 생각을 해보니

 

이동값의 최소를 구하는 문제가 아니였습니다.... 그저 최적!

 

이기는쪽에서는 빨리 끝내야하고

지는쪽에서는 조금이라도 더 끌어야하는 그런 경우....

 

a   1   1   0
1   1   0   1
1   0   1   1
0   1   1   b 

 

이렇게 나누어져 있는 경우 최소값은 각각 2칸씩 움직인 4가되지만

지는쪽에서는 최대한 최적으로 움직여야하기에 각각 4칸씩 움직인 8이 답이됩니다.

 

이제 문제를 알았고 최적을 어떻게 구할지 고민....

 

 

 

 

최적이란 A,B가 승리를 위해서 움직인다?

그렇다면 이 부분을 어떻게 나누어야하고.. 판단해야할까요..

 

 

 

결국 블로그 참고....

[2022 KAKAO Blind Recruitment] Q7. 사라지는 발판 (C++, Python, Java)

 

여기가 코드설명이 되게잘되어있는것 같아요!

 

 

 

위 블로그의 재귀탐색함수부분입니다.

int solve(vector<int> P1 , vector<int> P2){
    if(vis[P1[0]][P1[1]]){
        return 0;    
    } 
    
    int ret = 0;
    
    for(int i = 0; i < 4; i++){
        int nx = P1[0] + dx[i];
        int ny = P1[1] + dy[i];
        
        if(Check(nx,ny) || vis[nx][ny] || !block[nx][ny]){//범위 넘어가거나, 이미 지나왔거나, 블록칸이 0일때 
            continue;
        } 
        
        
        vis[P1[0]][P1[1]] = 1; // 플레이어가 직전에 있던 곳에 방문 표시를 남김
        int val = solve(P2,{nx,ny})+1;      
        vis[P1[0]][P1[1]] = 0;      
        
        // 1. 현재 저장된 턴은 패배인데 새로 계산된 턴은 승리인 경우
        if(ret % 2 == 0 && val % 2 == 1){
            ret = val; // 바로 갱신
        } 
        // 2. 현재 저장된 턴과 새로 계산된 턴이 모두 패배인 경우
        else if(ret % 2 == 0 && val % 2 == 0){
            ret = max(ret, val); // 최대한 늦게 지는걸 선택
        } 
        // 3. 현재 저장된 턴과 새로 계산된 턴이 모두 승리인 경우
        else if(ret % 2 == 1 && val % 2 == 1){
            ret = min(ret, val); // 최대한 빨리 이기는걸 선택
        }
        
    }
    return ret;
}

 

이중에서  다른 부분은 모두 구현했었지만 

 

제일 중요한 최적에대해서 판단, 체크하는 부분

 // 1. 현재 저장된 턴은 패배인데 새로 계산된 턴은 승리인 경우
        if(ret % 2 == 0 && val % 2 == 1){
            ret = val; // 바로 갱신
        } 
        // 2. 현재 저장된 턴과 새로 계산된 턴이 모두 패배인 경우
        else if(ret % 2 == 0 && val % 2 == 0){
            ret = max(ret, val); // 최대한 늦게 지는걸 선택
        } 
        // 3. 현재 저장된 턴과 새로 계산된 턴이 모두 승리인 경우
        else if(ret % 2 == 1 && val % 2 == 1){
            ret = min(ret, val); // 최대한 빨리 이기는걸 선택
        }

 

이 부분이 가장 중요한 핵심인것 같습니다.

 

반환 값이 짝수 : 플레이어가 패배함을 의미
반환 값이 홀수 : 플레이어가 승리함을 의미

이 두 사실을 통해

 

1. 현재 플레이어가 이길수 있는 경우가 생길시 이기는 경우로 갱신

2. 모두 패배로 계산된 경우는 최대한 늦게

3. 모두 이기는 거라면? 최대한 빨리

 

이렇게 나누어서 계산을 해주네요

 

 

 

ALL

!#include <bits/stdc++.h>
using namespace std;

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

int n, m;

bool Check(int x, int y){
    return x<0 || x>=n || y<0 || y>=m;
}

bool vis[5][5];
vector<vector<int>> block;

// 현재 상태에서 둘 다 최적의 플레이를 할 때 남은 이동 횟수
// 반환 값이 짝수 : 플레이어가 패배함을 의미, 홀수 : 플레이어가 승리함을 의미

int solve(vector<int> P1 , vector<int> P2){
    if(vis[P1[0]][P1[1]]){
        return 0;    
    } 
    
    int ret = 0;
    
    for(int i = 0; i < 4; i++){
        int nx = P1[0] + dx[i];
        int ny = P1[1] + dy[i];
        
        if(Check(nx,ny) || vis[nx][ny] || !block[nx][ny]){//범위 넘어가거나, 이미 지나왔거나, 블록칸이 0일때 
            continue;
        } 
        
        
        vis[P1[0]][P1[1]] = 1; // 플레이어가 직전에 있던 곳에 방문 표시를 남김
        int val = solve(P2,{nx,ny})+1;      
        vis[P1[0]][P1[1]] = 0;      
        
        // 1. 현재 저장된 턴은 패배인데 새로 계산된 턴은 승리인 경우
        if(ret % 2 == 0 && val % 2 == 1){
            ret = val; // 바로 갱신
        } 
        // 2. 현재 저장된 턴과 새로 계산된 턴이 모두 패배인 경우
        else if(ret % 2 == 0 && val % 2 == 0){
            ret = max(ret, val); // 최대한 늦게 지는걸 선택
        } 
        // 3. 현재 저장된 턴과 새로 계산된 턴이 모두 승리인 경우
        else if(ret % 2 == 1 && val % 2 == 1){
            ret = min(ret, val); // 최대한 빨리 이기는걸 선택
        }
        
    }
    return ret;
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    n = board.size();
    m = board[0].size();
    block = board;
    
    return solve(aloc,bloc);
}

 

 

 

이런 2인플레이 게임에서 최적을 구해줄때는

A,B 따로 보지 말고 한플레이어가 계속해서 최적을 찾아가며 플레이 한다고 생각해야겠네요!

 

 

 

틀린점이 있다면 댓 달아주세요!