[Programmers] 사라지는 발판

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/92345

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

비트 마스킹을 연습하기 좋은 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 주어진 board 정보를 기반으로 boardBit을 생성합니다.

-> ex) [[1, 1, 1], [1, 0, 1], [0, 1, 1]]이 주어졌을 경우 boardBit는 111101011을 십진수로 변환한 값

2. 재귀함수 func는 매개변수 {y, x}에 위치한 사람이 플레이어의 턴일 때 최선의 플레이를 진행했을 경우 턴 수와 승리 여부를 반환하는 함수입니다.

2.1 {y, x}에 위치한 사람이 더 이상 움직일 수 없다면 패배

2.2 {y, x}에 위치한 사람이 상대방과 같은 발판에 서 있다면 승리

2.3 턴을 소비한 뒤 상대방의 관점에서 func함수 호출

2.3.1 상대방이 승리를 못할 경우 본인이 승리한다고 표시하고 최적의 턴 수를 업데이트

2.3.2 상대방이 승리했고 본인이 아직 승리하는 케이스가 없을 경우 최대 턴 수 업데이트

2.4 무조건 승리하는 경우 최적의 턴수와 함께 승리 여부를 true로 표시하고 반환

2.4.1 무조건 패배하는 경우 최대 턴수와 함께 승리 여부 false로 표시하고 반환

 

	#include <string>
	#include <vector>
	#include <iostream>
	#include <algorithm>
	#include <climits>
	using namespace std;
	int N, M;
	typedef struct
	{
	int turn;
	bool winnable;
	} State;
	typedef struct
	{
	int y, x;
	} Dir;
	Dir moveDir[4] = { { 1, 0 },{ -1, 0 },{ 0, 1 },{ 0, -1 } };
	bool isInRange(int y, int x)
	{
	return y >= 0 && y < N && x >= 0 && x < M;
	}
	bool tileExists(int y, int x, int boardBit)
	{
	return boardBit & (1 << (N * M - (y * M + x + 1)));
	}
	int switchTile(int y, int x, int boardBit)
	{
	return boardBit ^ (1 << (N * M - (y * M + x + 1)));
	}
	bool canNotMove(int y, int x, int boardBit)
	{
	for (int k = 0; k < 4; k++)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (isInRange(nextY, nextX) && tileExists(nextY, nextX, boardBit))
	{
	return false;
	}
	}
	return true;
	}
	State func(int y, int x, int opponentY, int opponentX, int boardBit)
	{
	if (canNotMove(y, x, boardBit))
	{
	return { 0, false };
	}
	if (y == opponentY && x == opponentX)
	{
	return { 1, true };
	}
	bool winnable = false;
	int minTurn = INT_MAX;
	int maxTurn = 0;
	for (int k = 0; k < 4; k++)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if ((isInRange(nextY, nextX) && tileExists(nextY, nextX, boardBit)) == false)
	{
	continue;
	}
	boardBit = switchTile(y, x, boardBit);
	State opponentState = func(opponentY, opponentX, nextY, nextX, boardBit);
	boardBit = switchTile(y, x, boardBit);
	if (opponentState.winnable == false)
	{
	winnable = true;
	minTurn = min(minTurn, opponentState.turn);
	}
	else if (winnable == false)
	{
	maxTurn = max(maxTurn, opponentState.turn);
	}
	}
	int turn = winnable ? minTurn : maxTurn;
	return { turn + 1, winnable };
	}
	int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
	N = board.size();
	M = board[0].size();
	int boardBit = 0;
	for (int i = 0; i < N; i++)
	{
	for (int j = 0; j < M; j++)
	{
	if (board[i][j])
	{
	boardBit |= 1 << (N * M - (i * M + j + 1));
	}
	}
	}
	cout << boardBit << "\n";
	State result = func(aloc[0], aloc[1], bloc[0], bloc[1], boardBit);
	return result.turn;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~