[프로그래머스] 블록 게임

링크

https://programmers.co.kr/learn/courses/30/lessons/42894

프로그래머스

풀이

 

보드 위에 놓인 블록의 상태가 담긴 2차원 배열 board가 주어질 때, 검은 블록을 떨어뜨려 없앨 수 있는 블록 개수의 최댓값을 구해야 되는 문제이다.

 

이때 우리가 확인 해야되는 블록은 밑의 그림과 같은 가로와 세로 모양의 7개의 블록을 확인 하면 되는것을 알수 있는데.

 

 

 

이때 일단 우리가 여기 확인 할수 있는것은

6개중 4개는 배치된 블록이고, 2개는 새로 놓은 블록이여야 된다는 것을 알 수 있다.

그래서 map을 이용하여 이것을 확인 할수 있도록 하였다.

 

 

 

 

그리고 위의 모양만을 확인 하면 되는 것이기 때문에

보드의 맨 위에서 밑으로 탐색하여 놓여진 블록을 만나는 부분까지 모조리 우리가 놓아야하는 블록으로 채워버렸다.

 

 

 

 

 

 

 

 

 

이때 조건에 만족하는 블록을 찾았으면 블록을 지워주고

새로운 블록을 채워 주었다.

 

 

 

 

 

 

 

 

이렇게 (0, 0) 부터 탐색을 시작하면서 블록을 제거 해주면 된다.

 

그런데 이렇게 탐색을 한번만 하다보니  이렇게 블록이 겹쳐 있는 상황에서는 처리가 안되었는데.

 

 

그래서 왼쪽에서 오른쪽으로 한번만 탐색하지 않고. 

두 번을 탐색하여 완전히 블록을 지울수 있도록 했다.

 

 

 

 두 번 탐색하여 완전히 제거함

 

 

 

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<cmath>

#define SIZE 110
const int INF = 2e9;

using namespace std;

typedef long long int ll;

int EMPTY = 0;
int BLOCK = 222;

int b_size;

int garo(int x, int y, vector<vector<int>> &board) {
	map<int, int > m; int cnt = 0;
	if (x <= b_size - 2 && y <= b_size - 3) {
		// 0 0 0
		// 0 0 0  탐색
		for (int i = y; i < y + 3; i++) {
			m[board[x][i]]++;
			m[board[x + 1][i]]++;
		}



		if (m[BLOCK] == 2 && m.size() == 2 && m.begin()->first != 0) {
			cnt++;
			for (int j = y; j < y + 3; j++) {
				for (int i = 0; i < b_size; i++) {
					if (board[i][j] == m.begin()->first || board[i][j] == EMPTY || board[i][j] == BLOCK)
						board[i][j] = BLOCK;
					else
						break;
				}
			}
		}
	}
	return cnt;
}
bool sero(int x, int y ,vector<vector<int>> &board) {
	map<int, int> m;	int cnt = 0;
	if (x <= b_size - 3 && y <= b_size - 2) {
		// 0 0
		// 0 0
		// 0 0 탐색
		for (int i = x; i < x + 3; i++) {
			m[board[i][y]]++;
			m[board[i][y + 1]]++;
		}


	
		if (m[BLOCK] == 2 && m.size() == 2 && m.begin()->first != 0) {
			cnt++;
			for (int j = y; j < y + 2; j++) {
				for (int i = 0; i < b_size; i++) {
					if (board[i][j] == m.begin()->first || board[i][j] == EMPTY || board[i][j] == BLOCK)
						board[i][j] = BLOCK;
					else
						break;
				}
			}
		}
	}
	return cnt;
}

int solution(vector<vector<int>> board) {
	b_size = board.size();
	for (int j = 0; j < b_size; j++) {
		for (int i = 0; i < b_size; i++) {
        	//맨 위부터 놓여진 블록을 만날때까지 위에서 새로운 블록을 놓음
			board[i][j] = board[i][j] == EMPTY ? BLOCK : board[i][j];
			if (board[i][j] != BLOCK)
				break;
		}
	}

	int res = 0;
	for (int i = 0; i < b_size; i++) {
    	//놓여진 블록이 겹쳐 있을수 있기 때문에 2번 탐색 실시
		for (int k = 0; k < 2; k++) {
			for (int j = 0; j < b_size; j++) {
				res += garo(i, j, board);
				res += sero(i, j, board);
			}
		}
	}
	
	return res;
}