[Programmers] 블록 게임

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

프로그래머스

 

`3 * 2, 2 * 3 형태로 구성된 블록을 찾을 수 있으면 지운다`를 반복하는 알고리즘 문제였습니다.

 

알고리즘은 다음과 같습니다.

1. 각 열마다 `가장 위쪽 블록의 행 번호`를 추적하여 topRowInCol 배열에 업데이트합니다.

1.1 topRowInCol 배열은 실제 검사해야 할 행 범위를 빠르게 결정할 수 있도록 지원합니다.

 

2. 3 * 2 나 2 * 3 영역에서 다음 조건이 해당하면 블록을 제거해 줍니다.

• 빈칸이 정확히 두 개 (주어진 블록들이 직사각형이 되려면 빈칸을 두 개 검은색 블록으로 채워줘야 함)
• 나머지 칸이 전부 동일 블록

 

3. 블록을 제거할 때마다 topRowInCol 배열을 업데이트해 줍니다.

 

4. 위 과정을 한 횟차에서 아무 블록도 제거되지 않을 때까지 반복해 줍니다.

 

	#include <string>
	#include <vector>
	#include <iostream>
	#include <algorithm>
	using namespace std;
	vector<vector<int>> gameBoard;
	int boardSize;
	// 각 열에서 "제일 위쪽 블록의 행 번호"를 저장
	vector<int> topRowInCol;
	void updateTopRow(int col)
	{
	int row = 0;
	for (; row < boardSize; row++)
	{
	if (gameBoard[row][col] != 0)
	{
	break;
	}
	}
	topRowInCol[col] = row;
	}
	bool removeBlock3x2(int col)
	{
	if (col + 1 >= boardSize)
	{
	return false;
	}
	int maxRow = max(topRowInCol[col], topRowInCol[col + 1]);
	if (maxRow < 2 || maxRow >= boardSize)
	{
	return false;
	}
	int val = gameBoard[maxRow][col];
	int blankCnt = 0;
	for (int r = maxRow; r >= maxRow - 2; r--)
	{
	for (int c = col; c <= col + 1; c++)
	{
	if (gameBoard[r][c] != 0 && gameBoard[r][c] != val)
	{
	return false;
	}
	if (gameBoard[r][c] == 0)
	{
	blankCnt++;
	}
	}
	}
	// 빈 칸이 정확히 2개여야 함
	if (blankCnt != 2)
	{
	return false;
	}
	// 블록 제거
	for (int r = maxRow; r >= maxRow - 2; r--)
	{
	for (int c = col; c <= col + 1; c++)
	{
	gameBoard[r][c] = 0;
	}
	}
	for (int c = col; c <= col + 1; c++)
	{
	updateTopRow(c);
	}
	return true;
	}
	bool removeBlock2x3(int col)
	{
	if (col + 2 >= boardSize)
	{
	return false;
	}
	vector<int> rows = { topRowInCol[col], topRowInCol[col + 1], topRowInCol[col + 2] };
	int maxRow = -1;
	int minRow = boardSize * 2;
	for (int row : rows)
	{
	maxRow = max(maxRow, row);
	minRow = min(minRow, row);
	}
	int sameMaxRowCnt = 0;
	for (int row : rows)
	{
	if (row == maxRow)
	{
	sameMaxRowCnt++;
	}
	}
	if (sameMaxRowCnt != 2)
	{
	return false;
	}
	if (minRow < 0 || maxRow >= boardSize)
	{
	return false;
	}
	if (maxRow < 1)
	{
	return false;
	}
	int val = gameBoard[maxRow][col];
	int blankCnt = 0;
	for (int r = maxRow - 1; r <= maxRow; r++)
	{
	for (int c = col; c <= col + 2; c++)
	{
	if (gameBoard[r][c] != 0 && gameBoard[r][c] != val)
	{
	return false;
	}
	if (gameBoard[r][c] == 0)
	{
	blankCnt++;
	}
	}
	}
	if (blankCnt != 2)
	{
	return false;
	}
	// 블록 제거
	for (int r = maxRow - 1; r <= maxRow; r++)
	{
	for (int c = col; c <= col + 2; c++)
	{
	gameBoard[r][c] = 0;
	}
	}
	for (int c = col; c <= col + 2; c++)
	{
	updateTopRow(c);
	}
	return true;
	}
	int solution(vector<vector<int>> board) {
	gameBoard = board;
	boardSize = board.size();
	topRowInCol.assign(boardSize, 0);
	for (int col = 0; col < boardSize; col++)
	{
	updateTopRow(col);
	}
	int answer = 0;
	while (true)
	{
	int removeCnt = 0;
	for (int col = 0; col < boardSize; col++)
	{
	if (removeBlock3x2(col))
	{
	removeCnt++;
	}
	if (removeBlock2x3(col))
	{
	removeCnt++;
	}
	}
	if (removeCnt == 0)
	{
	break;
	}
	answer += removeCnt;
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE  

 

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