프로그래머스 - 사라지는 발판 (C++)

 

문제 링크

 

1. 개요

 처음 문제를 접했을 때, 단순히 DFS나 백트래킹 문제라고 생각했다. 하지만 "서로 최선의 플레이를 한다"라는 조건이 붙어 있어 일반적인 탐색과는 결이 다르다는 것을 느꼈다. 이는 단순히 이기는 것뿐만 아니라, '이기면 빨리 이겨야 하고, 지면 최대한 늦게 져야 한다'는 복합적인 조건을 구현해야 했기 때문입니다.

 

2. 구현 과정

2-1. 게임 이론과 미니맥스(Minimax)

 문제를 해결하기 위해 필요한 핵심 개념은 미니맥스(Minimax) 알고리즘이었다. 흔히 AI가 체스나 오목을 둘 때 사용하는 방식인데, 개념을 잡는 것이 중요했다.

• 나(Player): 이길 수 있다면 가장 **짧은 턴(Min)**으로 이기려 한다.
• 상대(Opponent): 내가 질 수밖에 없다면, 상대가 최선을 다해도 가장 **긴 턴(Max)**까지 버티려 한다.

즉, "상대방도 나만큼 똑똑해서 절대 실수하지 않는다"는 가정하에, 미래의 모든 수를 내다보고 현재의 수를 결정해야 했다. 이를 재귀 함수(DFS)로 구현하기로 설계했다.

 

2-2. 발판이 사라지는 타이밍

구현 초기 단계에서 치명적인 실수가 있었다. 캐릭터가 이동할 때 '도착할 발판'을 미리 지우고 재귀를 호출했던 것이다.

// [잘못된 생각]
missing[nxtR][nxtC] = true; // 갈 곳을 미리 지움
Solve(enemy, {nxtR, nxtC});

 

하지만 문제의 조건은 기존에 밟고 있던 발판이 사라진다는 것이었다. 그래서 도착할 곳을 지우면 논리적으로 말이 안 됙 ㅣ때문에, 현재 내 위치를 지우고 이동한 뒤 복구하는 백트래킹 방식으로 수정했다.

// [수정된 로직]
board[r][c] = 0; // 현재 내 발판 삭제
Solve(enemy, {nxtR, nxtC});
board[r][c] = 1; // 복구

 

2-3. 승패 판단 로직

 재귀 함수에서 돌아온 결과(result)를 처리하는 부분에서 로직이 꼬였다. "상대가 이겼으면 나도 이기는 건가?" 혹은 "이기는 길을 찾았는데, 다른 길에서 지면 지는 건가?" 하는 혼란이 있었다.

그래서 다시 정리해보았다.

 

• result.first == false (상대가 짐): 나는 이기는 경우다. 이럴 때는 min 함수로 최소 턴을 갱신한다.
• result.first == true (상대가 이김): 나는 지는 경우다. 이럴 때는 max 함수로 최대 턴을 갱신한다.

특히, "내가 이기는 길이 단 하나라도 있으면, 나는 무조건 그 길을 선택할 것"이므로, 반복문 안에서 canWin 변수가 한 번 true가 되면 다시 false로 덮어씌워지지 않도록 주의해야 했다.

 

3. 마무리

 여러 번의 수정을 거쳐 드디어 모든 테스트 케이스를 통과했다.

• 함수의 반환값: {승패 여부, 턴 수} 쌍으로 관리
• 턴 계산: 함수가 리턴할 때 +1을 해주어 이동 횟수 누적
• 최적의 플레이: 이길 땐 min, 질 땐 max 갱신

#include <string>
#include <vector>

#define MAX 7

using namespace std;

int R, C;
int dirs[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
int board[MAX][MAX];

bool IsIn(int r, int c)
{
    return 0 <= r && r < R && 0 <= c && c < C;
}

pair<bool, int> Solve(pair<int, int> myLoc, pair<int, int> enemyLoc)
{
    int r = myLoc.first;
    int c = myLoc.second;
    
    // 발판이 사라진 곳이라면 이길 수 없는 곳
    if (board[r][c] == 0)
        return { false, 0 };
    
    bool canWin = false; // 이길 수 있는 루트가 하나라도 있는지
    int minTurn = 9999; // 이기는 경우 최소 턴
    int maxTurn = 0; // 지는 경우 최대 턴
    
    bool canGo = false; // 갈 곳이 한 군데라도 있는지
    
    for (int i = 0; i < 4; ++i)
    {
        int nxtR = r + dirs[i][0];
        int nxtC = c + dirs[i][1];
        
        if (IsIn(nxtR, nxtC) && board[nxtR][nxtC] == 1)
        {
            canGo = true;
            
            // 현재 내 발판을 지우고 이동
            board[r][c] = 0;
            
            // 턴 넘기기: (상대 위치, 내 새로운 위치)
            pair<bool, int> result = Solve(enemyLoc, { nxtR, nxtC });
            
            // 백트래킹 (발판 복구)
            board[r][c] = 1;
            
            if (result.first == false)
            {
                // 상대방이 지는 경우 -> 내가 이기는 경우
                canWin = true;
                
                // 이길 때는 가장 빠르게 이겨야 한다.
                minTurn = min(minTurn, result.second);
            }
            else 
            {
                // 상대방이 이기는 경우 -> 내가 지는 경우
                // (이미 canWin이 true라면, 굳이 지는 경우인 maxTurn을 갱신할 필요도 사실 없음.
                //  나는 어차피 이기는 길(minTurn)을 택할 거니까.)
                
                // 지는 경우 최대 턴으로 버텨야 한다.
                maxTurn = max(maxTurn, result.second);
            }
        }
    }
    
    // 갈 곳이 없으면 패배
    if (canGo == false)
        return { false, 0 };
    
    // 이번 턴 +1을 해서 반환 (result.second는 다음 턴부터의 횟수. 이번에는 내가 움직였으니 리턴할 때 +1해야 함)
    if (canWin)
        return { true, minTurn + 1 };
    else
        return { false, maxTurn + 1 };
}

int solution(vector<vector<int>> inputBoard, vector<int> aloc, vector<int> bloc) {
    R = inputBoard.size();
    C = inputBoard[0].size();
    
    for (int r = 0; r < R; ++r)
    {
        for (int c = 0; c < C; ++c)
            board[r][c] = inputBoard[r][c];
    }
    
    pair<bool, int> result = Solve({ aloc[0], aloc[1] }, { bloc[0], bloc[1] });
    
    return result.second;
}

 

 

이 문제는 구현력뿐만 아니라, 재귀 함수의 상태 관리와 게임 이론의 조건을 코드로 번역하는 능력을 기르는 데 아주 큰 도움이 되었다. 다음에는 비슷한 유형이 나와도 당황하지 않고 "닥터 스트레인지"처럼 미래를 내다보는 설계를 할 수 있을 것 같다.