블록게임
문제 해석
NxN배열에 블록들이 위치해 있을 때, 제거할 수 있는 블록의 최대 수를 구하는 문제입니다.
위쪽에서 1x1크기의 검은 블록을 떨어뜨려 쌓을 수 있습니다.
이때, 검은 블록과 기존 블록을 합해 속이 꽉 채워진 직사각형을 만들 수 있다면 그 블록을 없앨 수 있습니다.
설계(20)
이 문제를 풀이하는 방식은 두가지를 생각해볼 수 있습니다.
첫번째로, 검은 블록을 실제로 떨어뜨려서 제거할 수 있는 블록들을 제거하는 방법입니다.
두번째로, 검은 블록을 떨어뜨리지 않고 제거할 수 있는 블록들을 찾는 방법입니다.
이 방법들은 모두 시뮬레이션을 하는 방식으로 별도의 알고리즘이 필요하지 않습니다.
처음에 첫번째 방법으로 생각해서 설계를 했는데, 더 복잡해지고 디버깅이 어려워졌습니다. 따라서 두번째 방법을 이용하기로 하였습니다.
블록이 채워지는 모양은 2x3, 3x2가 있습니다. 따라서 각각의 모양에 대해서 check함수를 통해 체크하는 방식을 사용하였습니다.
check함수에서 각 모양에서 빈 공간의 개수가 2개를 넘지 않고, 나머지가 같은 숫자로 채워지는지 확인을 합니다.
여기서 주의할 점은 검은 블록이 해당 좌표까지 떨어질 수 있는 지 체크를 해야합니다. 가장 위에서 해당 좌표 위까지 떨어뜨려봐서 중간에 어떤 블록에 의해 멈추면 false를 리턴하도록 하였습니다.
구현(40)
코드
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool is_possible(int x, int y,vector<vector<int> > board) {
for (int i = 0; i < x; i++) {
if (board[i][y] != 0) return false;
}
return true;
}
bool check(int x, int y, int h, int w,vector<vector<int> > &board) {
int cnt = 0;
int num = -1;
for (int i = x; i < x + h; i++) {
for (int j = y; j < y + w; j++) {
if (board[i][j] == 0) {
if (!is_possible(i, j,board)) return false;
cnt++;
if (cnt > 2) return false;
}
else {
if (num == -1) {
num = board[i][j];
}
else if (num != board[i][j]) return false;
}
}
}
for (int i = x; i < x + h; i++) {
for (int j = y; j < y + w; j++) {
board[i][j] = 0;
}
}
return true;
}
int solution(vector<vector<int>> board) {
int answer = 0;
int cnt;
int N = board.size();
while (1) {
cnt = 0;
for (int i = 0; i < N-1; i++) {
for (int j = 0; j < N - 1; j++) {
if (j < N - 2 && check(i, j, 2, 3,board)) cnt++;
if (i < N - 2 && check(i, j, 3, 2,board)) cnt++;
}
}
if (cnt == 0) return answer;
else answer += cnt;
}
}
디버깅
제출결과
마무리
속이 꽉찬 모양을 체크할 수 있는 방법을 생각해보아야하는 구현문제였습니다.