프로그래머스 Level 3 사라지는발판

사라지는발판 (프로그래머스 Level 3)

https://school.programmers.co.kr/learn/courses/30/lessons/92345

아예 감이 안온것 같다
막연히 ‘재귀’를 사용하면 될 것 같다는 생각은 하였지만
각 유저가 ‘최선’을 다해야 한다라는 점에서
구현을 어떻게 풀어나가야 할지 막막했다

이후, 블로그나 검색을 통해 코드를 확인하고,
일부 수정해보거나 건드려가며 이해를 해보려 최대한 노력하였다

게임이론, Minimax 에 대한 지식이 있으면 이해가 쉽다고 한다
동시에 ‘승리/패배’ 여부 및 ‘최소/ 최대 이동 횟수’ 또한
관리가 되어야 하는 문제였다

• 게임이론
  

  의사 결정자들 사이의 ‘전략적 상호 작용’을 분석하는 이론
  각각의 ‘플레이어’는 승리를 위해 ‘전략’을 선택한다
  즉, 이 문제에서 ‘A’ 와 ‘B’는 자신이 ‘승리’ 혹은 ‘패배’ 할지 모르나
  최선을 다한다
  ‘승리’하는 경우는 가능한 ‘적은 수’를 써서 승리하려 하며,
  ‘패배’하는 경우는 가능한 ‘많은 수’를 써서 패배하려 한다
  

• Minimax 알고리즘
  

  주로 2명의 플레이어가 ‘번갈아 가며’ 진행하는 제로섬 게임에 사용
  ‘트리’ 구조를 이용하여 게임의 모든 경우의 수를 표현
  Max : 내 차례일 때 최선의 선택을 함으로서 ‘높은 점수’를 얻으려 함
  Min : 상대 차례일 땐, 상대가 가능한 ‘낮은 점수’를 얻도록 유도
  전반적인 작동 방식은
  

  1. 트리 구조 표현
     
  2. 최대화와 최소화 (Min, Max)
     
  3. 후보 평가 : 말단 노드에서 점수를 계산해가며 올라옴
     
  4. 백트래킹 (반복하여 ‘첫 노드’의 움직임 결정)
     

문제를 풀며 가장 이해하기 어려웠던 것이 2가지였는데

1. pair<bool,int> 부분에서 int만 return 해도 될것 같아
   코드를 수정하여 제출하였더니, 예제는 통과하였는데 틀렸다
   ‘승리/패배’ 부분에 대한 ‘처리’가 필요하다는 점을 알게 되었다
   (int만 return하면, 단순히 최대/ 최소 횟수만 처리할 수 있으므로)
   
2. 재귀로 return 받은 부분과, 현재 자신이 return할 pair의 bool 부분에 대한 처리가
   이해하기 어려웠다
   정확히는 재귀로 return을 받은 부분은 ‘상대’의 승패 결과이므로
   해당 부분에서 상대의 패배가 확실하다면,
   ‘나’의 승리이므로 ‘승리 처리’를 해주고
   그렇지 않다면 ‘안전’하게 가능한 ‘많은 수’를 사용하려 한다는 부분이
   나중에 이해되었다
   

Code

#include <vector>
#include<limits.h>

using namespace std;

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

bool cant_move(vector<vector<int>>& board, int y, int x)
{
	const int height = board.size();
	const int width = board[0].size();

	for (int d = 0; d < 4; ++d)
	{
		int ny = y + dy[d];
		int nx = x + dx[d];

		if (ny >= 0 && nx >= 0 && ny < height && nx < width && board[ny][nx] == 1)
			return false;
	}
	return true;
}

pair<bool, int> play(vector<vector<int>>& board, int y1, int x1, int y2, int x2)
{
	// 움직일 수 없으면 패배
	if (cant_move(board, y1, x1) == true)
	{
		return { false, 0 }; 
	}

	pair<bool, int> ret = { false, 0 };

	const int height = board.size();
	const int width = board[0].size();

	// 자신의 발판이 0 인 경우는 '패배'하는 경우
	if (board[y1][x1] == 1)
	{
		int minT = INT_MAX;
		int maxT = 0;

		for (int d = 0; d < 4; ++d)
		{
			int ny = y1 + dy[d];
			int nx = x1 + dx[d];

			if (ny >= 0 && nx >= 0 && ny < height && nx < width && board[ny][nx] == 1)
			{
				board[y1][x1] = 0;
				// 다음 수를 상대에게 넘긴다
				auto result = play(board, y2, x2, ny, nx);
				bool win = result.first;
				int moveCount = result.second;

				board[y1][x1] = 1;

				// 상대가 지는 경우이므로
				// 내가 이길 수 있는 경우의 수 : 최소 움직임으로 플레이
				if (win == false)
				{
					ret.first = true;
					minT = min(minT, moveCount);
				}
				// 아직 내가 이길지 모름
				// 이것은 result.first가 false이며
				// 동시에 현재 시점의 플레이어는 아직
				// 승리하는 경우의 수를 찾지 못한 경우이다
				// 최대 움직임으로 플레이
				else if (ret.first == false)
				{
					maxT = max(maxT, moveCount);
				}
			}
		}

		bool isWin = ret.first;
		// 내가 이겼으므로 '최소값'을 반환
		if (isWin == true)
		{
			ret.second = minT + 1;
		}
		// 내가 졌으므로 최댓값을 반환
		else
		{
			ret.second = maxT + 1;
		}
	}

	return ret;
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
	// 시작은 a가 움직인다
	return play(board, aloc[0], aloc[1], bloc[0], bloc[1]).second;
}