[cpp]사라지는 발판 - 2022 카카오 블라인드 채용

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

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

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

움직일 차례인데 캐릭터의 상하좌우 주변 4칸이 모두 발판이 없거나 보드 밖이라서 이동할 수 없는 경우, 해당 차례 플레이어는 패배합니다.
두 캐릭터가 같은 발판 위에 있을 때, 상대 플레이어의 캐릭터가 다른 발판으로 이동하여 자신의 캐릭터가 서있던 발판이 사라지게 되면 패배합니다.
게임은 항상 플레이어 A가 먼저 시작합니다. 양 플레이어는 최적의 플레이를 합니다. 즉, 이길 수 있는 플레이어는 최대한 빨리 승리하도록 플레이하고, 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이합니다. '이길 수 있는 플레이어'는 실수만 하지 않는다면 항상 이기는 플레이어를 의미하며, '질 수밖에 없는 플레이어'는 최선을 다해도 상대가 실수하지 않으면 항상 질 수밖에 없는 플레이어를 의미합니다. 최대한 오래 버틴다는 것은 양 플레이어가 캐릭터를 움직이는 횟수를 최대화한다는 것을 의미합니다.

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

... 자세한 문제 예시는 문제 링크에서

---

 

 재귀를 이용해 모든 경우의 수를 다 따져보며 자기가 질 때는 최대한 늦게 지고, 자기가 이길 때는 최대한 빨리 이기는 선택을 하면 되는 문제입니다. 그럼 자기가 이기는지 지는지는 어떻게 아냐? 두 플레이어가 번갈아 가면서 수를 두기 때문에, 현재 플레이어의 턴이 지나고 홀수번의 턴이 지난 후 게임이 끝나면 현재 플레이어가 이기게 되고, 아니라면 상대 플레이어가 이기게 됩니다. 그래서 이를 판별하기 위해 Win이라는 함수를 정의를 하였습니다.

 

bool Win(int val) {
	return val % 2;
}

 

 현재 턴이 A인 경우에는 A의 말만을 움직이고, B인 경우에는 B의 말만을 움직입니다. 그래서 재귀를 통해 문제를 해결하는 solve 함수에 'isA'라는 bool 타입 변수를 두어 턴을 구분하고, 해당 턴에 게임을 진행하는 플레이어의 위치만을 갱신할 수 있도록 재귀문을 구성하였습니다. 또한 재귀문을 통해 턴을 수행할때는 플레이어가 밟았던 칸을 표시하기 위해 'vis' 2차원 배열을 사용하였으며, 이미 밟은 칸은 true로 설정하고 해당 케이스가 백트래킹 되고 노드를 타고 올라오면서 밟았던 칸을 다시 false로 설정하므로 다른 케이스에서 vis배열을 사용할 수 있게 하였습니다. 매 턴이 수행되며 턴의 수를 1 더해줘야 하기 때문에, 재귀문의 결과에 1을 더해 newRst(현재 결과)에 저장하였습니다.

 

if (isA) { aloc = { nx, ny }; }
else { bloc = { nx, ny }; }

vis[currX][currY] = true;
int newRst = solve(board, aloc, bloc, !isA) + 1;
vis[currX][currY] = false;

 

 마지막으로 아까 만들었던 Win 함수를 이용하여 승패 결과를 갱신합니다. 문제에 써있듯이 양 플레이어는 항상 최적의 플레이를 합니다. 이길수 있는 플레이어는 빨리 이길려고 하고, 질 수밖에 없는 플레이어는 최대한 오래 버티려고 합니다. 이 내용을 베이스로 게임을 진행하는 턴 수를 저장해주면 됩니다.

 

if (!Win(rst) && Win(newRst)) rst = newRst;
else if (!Win(rst) && !Win(newRst)) rst = max(rst, newRst);
else if (Win(rst) && Win(newRst)) rst = min(rst, newRst);

 

 알아보기 쉽게 and문의 좌측에는 기존에 저장되어있는 최적의 플레이 결과를 저장하고, 우측에는 새로 플레이한 결과를 두어 조건문을 구성하였습니다. 위부터 순서대로 조건문을 해석하면 쉽게 이해하실 수 있을 겁니다.

 

1. 기존(rst)에는 패배했지만 새로 계산한 결과(newRst)에서는 승리한 경우: 기존 결과를 갱신. 승리할 수 있으면 패배한 경우는 전혀 생각하지 않는다.

2. 기존에도 현재에도 패배한 경우: 최대한 오래 버티기 위하여 최대값(max)을 저장

3. 기존에도 이기고 현재에도 이긴 경우: 가장 빠르기 승리하기 위해 최솟값(min)을 저장

4. 기존에는 승리했지만 현재에는 패배한 경우: 최적의 플레이만 생각할거기 때문에 이런건 생각하지 않는다

 

 

이를 조합하면 전체 코드를 구성할 수 있습니다. 인공지능(딥러닝 말고)을 공부하신 분이라면 친숙한 내용이셨을듯 한 문제였습니다.

 

 

전체코드

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

int r, c;
bool vis[5][5];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

bool Win(int val) {
	return val % 2;
}

// 홀수번: 내가 이김
// 짝수번: 상대가 이김
int solve(vector<vector<int>> &board, vector<int> aloc, vector<int> bloc, bool isA) {
	int currX = -1, currY = -1, rst = 0;

	if (isA) { currX = aloc[0], currY = aloc[1]; }
	else { currX = bloc[0], currY = bloc[1]; }

	if (vis[currX][currY]) return 0;

	for (int i = 0; i < 4; ++i) {
		int nx = currX + dx[i];
		int ny = currY + dy[i];

		if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
		if (!board[nx][ny] || vis[nx][ny]) continue;

		if (isA) { aloc = { nx, ny }; }
		else { bloc = { nx, ny }; }

		vis[currX][currY] = true;
		int newRst = solve(board, aloc, bloc, !isA) + 1;
		vis[currX][currY] = false;

		if (!Win(rst) && Win(newRst)) rst = newRst;
		else if (!Win(rst) && !Win(newRst)) rst = max(rst, newRst);
		else if (Win(rst) && Win(newRst)) rst = min(rst, newRst);
	}

	return rst;
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
	r = board.size(); c = board[0].size();
	return solve(board, aloc, bloc, true);
}

 

 

코딩테스트 연습 - 사라지는 발판