[프로그래머스 C++] 2018 카카오 1차 프렌즈4블록

문제 : 프렌즈4블록

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 프렌즈4블록.
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

위 초기 배치를 문자로 표시하면 아래와 같다.

 

TTTANT

RRFACC

RRRFCC

TRRRAA

TTMMMF

TMMTTJ

 

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다.

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

 

 분석

'4블록'이 기준이다. 2x2로 나눴을 때, 좌하단을 기준으로 판단해가면 지울 블록은 쉽게 찾을 수 있다.

문제는 지워진 다음에 아래로 떨어지는 블록들이다.

 

필자는 먼저 지워지는 데이터를 저장한 다음에, 보드판을 column 기준으로 검사를 해서 없어지는 칸은 'x' 데이터로 채웠다.

 

예시

 구현

column별로 데이터를 처리할 때, 평소 사용하던 인덱스와는 다르므로 좀 더 주의하자.

using namespace std;

bool check[30][30] = { false };
bool check_squear(int m, int n, const vector<string>& board)
{
	bool game_over = true;
	// 2x2 에서 좌하단에서만 확인.
	for (size_t i = 1; i < m; i++)
	{
		for (size_t j = 1; j < n; j++)
		{
			char tmp = board[i][j];

			// x는 비어있는 칸
			if (tmp == 'x') continue;

			if (tmp == board[i - 1][j - 1] && tmp == board[i - 1][j]
				&& tmp == board[i][j - 1])
			{
				check[i - 1][j - 1] = true;
				check[i - 1][j] = true;
				check[i][j - 1] = true;
				check[i][j] = true;
				game_over = false;
			}
		}
	}
	return game_over;
}


int solution(int m, int n, vector<string> board)
{
	int answer = 0;

	while (!check_squear(m, n, board))
	{
		// column 별로 칸 확인 후 삭제
		for (size_t i = 0; i < n; i++)
		{
			vector<char> tmp;
			int tmp_cnt = 0;

			// 없어질 칸 확인
			for (size_t j = 0; j < m; j++)
			{
				if (!check[j][i])
				{
					tmp.push_back(board[j][i]);
				}
				else if(check[j][i] && board[j][i] != 'x')
				{
					answer++;
					tmp_cnt++;
				}
			}
			
			/*
			확인용 출력
			cout << "------------\n";
			for (size_t n = 0; n < tmp.size(); n++)
			{
				cout << tmp[n] << '\n';
			}
			cout << "------------\n";
			*/

			// pop후 board 재배열
			for (size_t j = 0; j < m; j++)
			{
				if (j < tmp_cnt) board[j][i] = 'x';
				else
				{
					board[j][i] = tmp.front();
					tmp.erase(tmp.begin());
				}
			}
		}

		// check 초기화
		memset(check, 0, sizeof(check));
	}

	return answer;
}

int main()
{
	vector<string> board = { "CCBDE", "AAADE", "AAABF", "CCBBF" };
	cout << solution(4, 5, board); // 14
	return 0;
}