[프로그래머스] 사라지는 발판 풀이 (2022 카카오 코딩테스트)

| |
프로그래머스 - 사라지는 발판 C++ 풀이 (2022 카카오 블라인드 채용 1차 코딩테스트)


문제 설명

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

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

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

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

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

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

0

위와 같은 경우, 플레이어 A는 실수만 하지 않는다면 항상 이길 수 있습니다. 따라서 플레이어 A는 이길 수 있는 플레이어이며, B는 질 수밖에 없는 플레이어입니다. 다음은 A와 B가 최적의 플레이를 하는 과정을 나타냅니다.

  1. 플레이어 A가 초기 위치 (1, 0)에서 (1, 1)로 이동합니다. 플레이어 A가 (0, 0)이나 (2, 0)으로 이동할 경우 승리를 보장할 수 없습니다. 따라서 무조건 이길 방법이 있는 (1, 1)로 이동합니다.

  2. 플레이어 B는 (1, 1)로 이동할 경우, 바로 다음 차례에 A가 위 또는 아래 방향으로 이동하면 발판이 없어져 패배하게 됩니다. 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이하기 때문에 (1, 1)로 이동하지 않습니다. (1, 2)에서 위쪽 칸인 (0, 2)로 이동합니다. A가 (1, 1)에서 (0, 1)로 이동합니다. B에게는 남은 선택지가 (0, 1)밖에 없습니다. 따라서 (0, 2)에서 (0, 1)로 이동합니다. A가 (0, 1)에서 (0, 0)으로 이동합니다. 이동을 완료함과 동시에 B가 서있던 (0, 1)의 발판이 사라집니다. B가 패배합니다. 만약 과정 2에서 B가 아래쪽 칸인 (2, 2)로 이동하더라도 A는 (2, 1)로 이동하면 됩니다. 이후 B가 (2, 1)로 이동, 다음 차례에 A가 (2, 0)으로 이동하면 B가 패배합니다. 위 예시에서 양 플레이어가 최적의 플레이를 했을 경우, 캐릭터의 이동 횟수 합은 5입니다. 최적의 플레이를 하는 방법은 여러 가지일 수 있으나, 이동한 횟수는 모두 5로 같습니다.

게임 보드의 초기 상태를 나타내는 2차원 정수 배열 board와 플레이어 A의 캐릭터 초기 위치를 나타내는 정수 배열 aloc, 플레이어 B의 캐릭터 초기 위치를 나타내는 정수 배열 bloc이 매개변수로 주어집니다. 양 플레이어가 최적의 플레이를 했을 때, 두 캐릭터가 움직인 횟수의 합을 return 하도록 solution 함수를 완성해주세요.


제한 사항

  • 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이 같을 수 있습니다.
  • 상대 플레이어의 캐릭터가 있는 칸으로 이동할 수 있습니다.


풀이

2022 카카오 블라인드 1차 코딩테스트의 마지막 문제이다. 문제를 처음 보고 알고리즘 대회에서나 보던 게임 이론 문제가 기업 코딩테스트에 출몰해서 꽤 놀랐다. 그런데 실제 코딩테스트 이후 문제가 공개되고 난 후 다시 확인해보니 문제의 유형 자체가 게임 이론이라기보단 문제 아이디어만 그쪽에서 가져온 느낌이었다. 보통 게임 이론 문제의 경우, 게임판의 상태에 따른 결과를 DP 기법을 통해 저장해나간다. 이때 게임판의 상태를 정수와 같은 간단한 형태로 변환하기 위해 비트마스킹을 사용하거나 고난이도 문제의 경우 스프라그-그런디 이론까지 이용하기도 한다. 하지만 본 문제의 경우 게임판 상태의 경우의 수가 현저히 적어 DP도 사용할 필요 없이 완전 탐색으로도 해결이 가능했다.

카카오가 게임 이론 문제의 난이도를 하향함으로써 코딩테스트의 수준에 맞추려던 의도로 보인다. 하지만 그렇다고 해서 본 문제가 완전 탐색만을 알고 있다고 해서 풀 수 있는 문제는 아니었다. 게임 이론을 접해보지 못했다면 아이디어를 떠올리기 쉽지 않았을 것이다. 그런데 본 문제는 앞에서도 언급했다 시피 게임 이론 자체보다는 완전 탐색에 중점을 둔 문제이기 때문에 구현력도 상당히 중요한 문제였다.

본 문제와 통상적인 게임 이론 문제의 가장 큰 차이점은 누가 이기는지를 구하는 것이 아닌 턴을 얼마나 이어가는지를 구한다는 것이다. 또한 양쪽이 최선의 플레이를 한다는 조건 대신 최적의 플레이를 한다는 조건이 주어지는데, 이때 최적이란 양쪽이 최선의 플레이를 했을 때 이기는 쪽은 게임 턴 수를 최소화시키려 하고, 지는 쪽은 최대화시키는 것이다.

따라서 누가 이기는지에 대한 정보 뿐만 아니라 턴 수에 대한 정보도 필요하기 때문에 만약 DP를 사용해야하는 문제였다면 DP 배열을 잡기 쉽지 않았을 것이다. 게임판의 최대 경우의 수를 나이브하게 계산해보면 2^25 * 25 * 25로 완전 탐색을 사용할 수 없을 것처럼 보이지만, 플레이어가 움직일 때 마다 발판이 사라지므로 게임 트리의 깊이가 굉장히 얕다. 따라서 완전 탐색을 이용해도 충분히 구할 수 있다. 하지만 실전이었다면 당연히 이러한 판단은 할 수 없고 어떻게 해서든 DP를 적용하려 하거나 지푸라기라도 잡는 심정으로 완전 탐색 코드를 제출해서 우연히 얻어걸렸을 것이다.

Top-down 형식의 재귀를 사용하여 완전 탐색을 할 것이다. 다음과 같은 재귀 함수를 정의한다.

solve(board, y1, x1, y2, x2) = (y1,x1)에 위치한 플레이어의 턴일 때 최선의 플레이 시 승리 여부와 최적의 플레이 시 턴 수

플레이어가 두 명 있기 때문에 재귀 함수를 2개 선언하거나 하나의 재귀 함수에 수많은 if문을 때려박을 수 있는데, 플레이어 좌표 매개변수의 순서를 고정하지 말고 위와 같이 하면 코드양을 줄일 수 있다.

기저 사례로는 문제에서 언급한 게임이 끝나는 2가지 조건에 대해 정의해준다. A의 차례일 때 움직일 수 없다면 A가 패배하고, 움직일 수 있으면서 A와 B가 같은 발판에 있다면 A가 어디로 움직이던 간에 다음 턴에 B가 패배한다. 이 이후 모든 경우의 수를 탐색하며 승리할 수 있을 시엔 최소 턴 수를 반환하고, 무조건 패배할 시에는 최대 턴 수와 함께 반환해주면 된다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <vector>
using namespace std;

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

bool inRange(int y, int x) {
    return 0<= y && y < N && 0 <= x && x < M;
}

// can't move
bool isFinished(vector<vector<int>>& board, int y, int x) {
    for(int i=0; i<4; i++) {
        int ny = y+dy[i];
        int nx = x+dx[i];
        if(inRange(ny,nx) && board[ny][nx])
            return false;
    }
    return true;
}

// {canWin, turn}
pair<bool, int> solve(vector<vector<int>>& board, int y1, int x1, int y2, int x2) {
    // base case
    if(isFinished(board, y1, x1)) return {false, 0};
    if(y1==y2 && x1==x2) return {true, 1};
    
    bool canWin = false;
    int minTurn = 1e9, maxTurn = 0;
    
    for(int i=0; i<4; i++) {
        int ny = y1+dy[i];
        int nx = x1+dx[i];
        if(!inRange(ny,nx) || !board[ny][nx]) continue;
        
        // dfs
        board[y1][x1] = 0;
        pair<bool, int> res = solve(board, y2, x2, ny, nx);
        board[y1][x1] = 1;

        // 이때 res는 상대편에 대한 결과이므로 반대로 생각
        if(!res.first) {
            canWin = true;
            minTurn = min(minTurn, res.second + 1);
        }
        else if(!canWin) {
            maxTurn = max(maxTurn, res.second + 1);
        }
    }
    
    return {canWin, (canWin ? minTurn : maxTurn)};
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    N = board.size(), M = board[0].size();

    return solve(board, aloc[0], aloc[1], bloc[0], bloc[1]).second;
}
0%