(2022 KAKAO BLIND) 사라지는 발판
문제 설명
플레이어 A와 플레이어 B가 서로 게임을 합니다. 당신은 이 게임이 끝날 때까지 양 플레이어가 캐릭터를 몇 번 움직이게 될지 예측하려고 합니다.
각 플레이어는 자신의 캐릭터 하나를 보드 위에 올려놓고 게임을 시작합니다. 게임 보드는 1x1 크기 정사각 격자로 이루어져 있으며, 보드 안에는 발판이 있는 부분과 없는 부분이 있습니다. 발판이 있는 곳에만 캐릭터가 서있을 수 있으며, 처음 캐릭터를 올려놓는 곳은 항상 발판이 있는 곳입니다. 캐릭터는 발판이 있는 곳으로만 이동할 수 있으며, 보드 밖으로 이동할 수 없습니다. 밟고 있던 발판은 그 위에 있던 캐릭터가 다른 곳으로 이동하여 다른 발판을 밞음과 동시에 사라집니다. 양 플레이어는 번갈아가며 자기 차례에 자신의 캐릭터를 상하좌우로 인접한 4개의 칸 중에서 발판이 있는 칸으로 옮겨야 합니다.
다음과 같은 2가지 상황에서 패자와 승자가 정해지며, 게임이 종료됩니다.
- 움직일 차례인데 캐릭터의 상하좌우 주변 4칸이 모두 발판이 없거나 보드 밖이라서 이동할 수 없는 경우, 해당 차례 플레이어는 패배합니다.
- 두 캐릭터가 같은 발판 위에 있을 때, 상대 플레이어의 캐릭터가 다른 발판으로 이동하여 자신의 캐릭터가 서있던 발판이 사라지게 되면 패배합니다.
게임은 항상 플레이어 A가 먼저 시작합니다. 양 플레이어는 최적의 플레이를 합니다. 즉, 이길 수 있는 플레이어는 최대한 빨리 승리하도록 플레이하고, 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이합니다. ‘이길 수 있는 플레이어’는 실수만 하지 않는다면 항상 이기는 플레이어를 의미하며, ‘질 수밖에 없는 플레이어’는 최선을 다해도 상대가 실수하지 않으면 항상 질 수밖에 없는 플레이어를 의미합니다. 최대한 오래 버틴다는 것은 양 플레이어가 캐릭터를 움직이는 횟수를 최대화한다는 것을 의미합니다.
아래 그림은 초기 보드의 상태와 각 플레이어의 위치를 나타내는 예시입니다.
위와 같은 경우, 플레이어 A는 실수만 하지 않는다면 항상 이길 수 있습니다. 따라서 플레이어 A는 이길 수 있는 플레이어이며, B는 질 수밖에 없는 플레이어입니다. 다음은 A와 B가 최적의 플레이를 하는 과정을 나타냅니다.
- 플레이어 A가 초기 위치 (1, 0)에서 (1, 1)로 이동합니다. 플레이어 A가 (0, 0)이나 (2, 0)으로 이동할 경우 승리를 보장할 수 없습니다. 따라서 무조건 이길 방법이 있는 (1, 1)로 이동합니다.
- 플레이어 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이 같을 수 있습니다.
- 상대 플레이어의 캐릭터가 있는 칸으로 이동할 수 있습니다.
문제 풀이
처음 보는 문제 형식이었고 문제의 구문도 굉장히 애매모호하게 적혀있어 많이 헤멘 문제였다. 문제의 설명만 보면 A와 B 둘중 한명이 ‘무조건 이기는 플레이어’로 지정되어 있고 한쪽은 ‘무조건 지는 플레이어’로 지정되어 있어 둘 중 어느 쪽이 ‘무조건 이기는 플레이어’인지 찾아내서 계산해야할 것 같지만 사실 그런건 없다.
내가 이해를 못하는건진 잘 모르겠지만 일단 내가 이해하기 쉽게 풀어 써본다면 ‘각 플레이어는 이기는 수가 있다면 항상 이기는 수를 두고 현재 상황에서 질 수밖에 없다면 지는데까지 걸리는 턴이 최대인 수를 둔다’가 맞는 것 같다. 다시말해 두 플레이어는 언제나 최선의 수를 두고 최선의 수가 없다면 가장 오래 걸리는 턴을 반환하면 되는 것이다.
그리고 이 게임에서는 승리 조건이 따로 없고 패배 조건만 존재한다. 따라서 내가 두는 이 수가 이기는 수인지는 상대가 패배할 수 밖에 없는가를 계산하여 판단해야 한다.
결론적으로 우리는 dfs를 통하여 상하좌우로 움직이면서 이렇게 움직였을 때 상대가 질 수밖에 없는지, 아니면 이기는 수가 있는지를 재귀함수를 통해 계산하여 상하좌우 4번의 이동 중 내가 이기는 수가 있다면 이기는 수 중에서 최소 턴을 반환하고 4번의 이동 중 지는 수밖에 없다면 지는 수 중에서 최대 턴을 반환하면 되는 것이다.
내가 이해한대로 썼지만 다른사람이 이것을 읽고 이해가 될지는 잘 모르겠다. 나도 정답을 읽고도 이해하는데 한참이 걸렸기 때문에 어쩔 수 없는 부분같다. 나는 이 문제를 통해 게임이론, minimax 알고리즘 등의 단어를 처음 듣게 되었는데 minimax 알고리즘은 이 문제의 풀이과정과 상당히 유사하다.
minimax 알고리즘에 대해 간단히 설명하자면 ‘상대의 턴의 이익을 최소화하고 내 턴의 이익을 최대화하는 알고리즘’ 이라 할 수 있다.
일단 체스나 틱택토 등 턴제 게임을 한다고 가정하고 루트 노드에 현재의 수, 자식 노드들에 현재의 수로부터 파생되는 미래의 수들을 가진 트리를 만들고, 각 노드에 상황이 얼마나 유리한지를 숫자로 환산한 것을 붙인다. 두 플레이어는 항상 최선의 수를 둔다고 가정한다. 그리고 트리를 끝에서부터 역행하며 상대의 턴이라면 나에게 가장 불리한 수를 택할 것이므로 환산치가 가장 작은 것(min)을 올리고 나의 턴이라면 나에게 가장 유리한 수를 택할 것이므로 환산치가 가장 큰 것(max)를 올린다. 그렇게 계속해서 올리다보면 루트 노드의 현재 수의 환산값을 알 수 있게 된다.
이길 수 있다면 가장 작은 턴을, 진다면 가장 큰 턴을 반환하는 이 문제와 상당히 유사하지 않은가?
결과적으로 문제 자체는 이해 풀이 모두 굉장히 어려웠지만 내가 전혀 몰랐던 여러 이론을 접할 수 있어 매우 유익한 문제였다.
코드
#include <string>
#include <vector>
using namespace std;
int N, M;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool inrange(int x, int y) {
return x<N && x>=0 && y<M && y>=0;
} //현재 픽한 노드가 범위 안에 있는지
bool unmove(vector<vector<int>> board, int x, int y) {
for(int i=0; i<4; i++) {
int xx=x+dx[i];
int yy=y+dy[i];
if(inrange(xx,yy) && board[xx][yy]) return false;
}
return true;
} //현재 위치에서 이동할 수 있는 발판이 있는지
pair<bool, int> simul(vector<vector<int>> board, int x1, int y1, int x2, int y2) {
if(unmove(board,x1,y1)) return {false, 0}; //주변에 발판이 없으면 즉시 패배하므로 false, 0을 반환
pair<bool, int> res={false, 0};
if(board[x1][y1]) { //현재 위치에 발판이 없어도 패배하므로 즉시반환
int mint=100000; int maxt=0;
for(int i=0; i<4; i++) {
int xx=x1+dx[i];
int yy=y1+dy[i];
if(!inrange(xx,yy) || unmove(board, xx, yy)) continue;
board[x1][y1]=0;
pair<bool, int> tmp=simul(board,x2,y2,xx,yy); //다음턴 상대의 상태 계산
board[x1][y1]=1;
if(!tmp.first) {
res.first=true;
mint=min(mint,tmp.second+1);
} //상대가 지는 수밖에 없다면 내가 승리, 최소턴 반환
else if(tmp.first) {
maxt=max(maxt,tmp.second+1);
} //상대에게 이기는 수가 있다면 나는 자동으로 패배, 최대턴 반환
if(res.first) res.second=mint;
else res.second=maxt;
}
}
return res;
}
int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
N=board.size(); M=board[0].size();
int answer=simul(board,aloc[0],aloc[1],bloc[0],bloc[1]).second;
return answer;
}