[Programmers] [1차] 프렌즈4블록

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

코딩테스트 연습 - [1차] 프렌즈4블록

백준 11499번 Puyo Puyo(https://jaimemin.tistory.com/722)와 비슷한 문제였습니다.

 

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

1. 좌상단에서 우하단으로 순차적으로 탐색을 진행하며 깨뜨릴 수 있는 블록들의 좌상단 좌표들을 큐에 넣어줍니다.

2. 해당 좌표들에 'X' 표시를 해주며 표시를 하면서 개수를 파악합니다.

3. X 좌표가 있는 블록이 있을 때 블록들을 위에서부터 아래로 한 칸씩 내려줍니다.

3.1 이 떄, 빈 블록에 대해서는 ' ' 표시를 해줍니다.

3.2  2번에서 파악한 개수를 반환해줍니다.

4. eraseBlock 메서드를 수행했을 때 꺠드린 블록이 0개가 될 때까지 1 ~ 3.2를 반복해줍니다.

5. 4번 과정을 거쳤을 때 깨드린 총 블록 개수를 반환해줍니다.

 

	#include <string>
	#include <vector>
	#include <queue>
	#include <iostream>
	using namespace std;
	typedef struct
	{
	int y, x;
	char character;
	} Block;
	int eraseBlocks(vector<string> &board)
	{
	queue<pair<int, int>> q;
	for (int y = 0; y < board.size() - 1; y++)
	{
	for (int x = 0; x < board[y].length() - 1; x++)
	{
	char block = board[y][x];
	if (block == ' ')
	{
	continue;
	}
	if (board[y + 1][x] == block
	&& board[y][x + 1] == block
	&& board[y + 1][x + 1] == block)
	{
	q.push({ y, x });
	}
	}
	}
	int cnt = 0;
	while (!q.empty())
	{
	int y = q.front().first;
	int x = q.front().second;
	q.pop();
	if (board[y][x] != 'X')
	{
	cnt++;
	board[y][x] = 'X';
	}
	if (board[y + 1][x] != 'X')
	{
	cnt++;
	board[y + 1][x] = 'X';
	}
	if (board[y][x + 1] != 'X')
	{
	cnt++;
	board[y][x + 1] = 'X';
	}
	if (board[y + 1][x + 1] != 'X')
	{
	cnt++;
	board[y + 1][x + 1] = 'X';
	}
	}
	for (int y = board.size() - 1; y >= 1; y--)
	{
	for (int x = 0; x < board[y].length(); x++)
	{
	if (board[y][x] != 'X')
	{
	continue;
	}
	while (board[y][x] == 'X')
	{
	queue<Block> blockQ;
	for (int curY = y - 1; curY >= 0; curY--)
	{
	blockQ.push({ curY, x, board[curY][x] });
	}
	while (!blockQ.empty())
	{
	int curY = blockQ.front().y;
	int curX = blockQ.front().x;
	char curCharacter = blockQ.front().character;
	blockQ.pop();
	board[curY + 1][curX] = curCharacter;
	board[curY][curX] = ' ';
	}
	}
	}
	}
	return cnt;
	}
	int solution(int m, int n, vector<string> board) {
	int answer = 0;
	while (1)
	{
	int cnt = eraseBlocks(board);
	if (cnt == 0)
	{
	break;
	}
	answer += cnt;
	}
	return answer;
	}
	int main(void)
	{
	int m = 4;
	int n = 5;
	vector<string> board = { "CCBDE", "AAADE", "AAABF", "CCBBF" };
	cout << solution(m, n, board) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

 

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