[구현] (프로그래머스 Lv 4) 블록 게임

문제

• 문제 링크
• 문제 설명: 왼쪽 그림에 소개된 블록들만 배치된 2차원 배열 보드가 주어질 때 오른쪽 그림과 같이 검은 블록을 떨어뜨려 속이 꽉 찬 직사각형을 만들어 없앨 수 있다. 이 때 제거 가능한 블록의 최대 개수를 반환하는 함수를 작성하라.

• 입력: 보드의 원소는 0~200 사이의 자연수이며 0은 빈칸, 나머지 숫자는 블록의 번호이다.
• 출력: 제거 가능한 블록의 최대 개수

board	result
[[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]]	2

풀이

• 없앨 수 있는 블록은 아래 그림처럼 위가 비어있으면서 블록 위쪽에 다른 블록이 없는 경우

• 블록의 모양을 확인하는 방법
  • 아래와 같이 블록 번호별로 좌표를 순서대로 저장하면 좌표를 비교해서 블록 모양을 알아낼 수 있음

vector<pii> v[201]; // 블록당 좌표
for (int y = 0; y < N; y++)
    for (int x = 0; x < N; x++)
        if (board[y][x] > 0)
            v[board[y][x]].push_back({y, x});

각 블록마다 4개의 좌표가 저장되고, 좌표 배열 인덱스를 순서로 쓸 수 있다

• canDelete(block) := Y좌표값과 X좌표값을 비교하여 블록 모양을 검사한 뒤 위쪽에 막고 있는 블록이 없는지 검사하여 검은 블록을 모두 놓을 수 있으면 true를 반환, 아니면 false
• 블록은 위쪽부터 하나씩 없애야 가장 많이 없앨 수 있기 때문에 차례대로 제거해준다.
• 정답 코드

#include <string>
#include <vector>
#define Y first
#define X second
using namespace std;
typedef pair<int,int> pii;

vector<pii> v[201]; // 블록당 좌표
int N;

bool canDelete(int block, vector<vector<int>>& board) {
    vector<pii> c = v[block];
    if (c[1].Y == c[2].Y and c[1].Y == c[3].Y) { // 아래 3개의 사각형, 위에 1개 사각형 있는 경우
        if (c[0].Y + 1 == c[1].Y) {
            int tmp[2];
            if (c[0].X == c[1].X) tmp[0] = c[2].X, tmp[1] = c[3].X;
            else if (c[0].X == c[2].X) tmp[0] = c[1].X, tmp[1] = c[3].X;
            else if (c[0].X == c[3].X) tmp[0] = c[1].X, tmp[1] = c[2].X;
            for (int i = c[0].Y; i >= 0; i--)
                if (board[i][tmp[0]] > 0 or board[i][tmp[1]] > 0)
                    return false;
            return true;
        }
    } else if (c[0].X == c[1].X and c[2].Y == c[3].Y) { // 세로로 3개 사각형이 있는 경우
        int tmp;
        if (c[0].X == c[2].X) tmp = c[3].X;
        else if (c[0].X == c[3].X) tmp = c[2].X;
        else return false;
        for (int i = c[2].Y-1; i >= 0; i--)
            if (board[i][tmp] > 0) return false;
        return true;
    }
    return false;
}

int solution(vector<vector<int>> board) {
    int answer = 0;
    N = board.size();
    for (int y = 0; y < N; y++)
        for (int x = 0; x < N; x++)
            if (board[y][x] > 0)
                v[board[y][x]].push_back({y, x});
    
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++) {
            int& blockNumber = board[y][x];
            if (blockNumber > 0) {
                if (canDelete(blockNumber, board)) {
                    answer++;
                    // 블록 제거
                    for (auto& p : v[blockNumber]) board[p.Y][p.X] = 0;
                }
            }
        }
    }
    return answer;
}