2019 Kakao blind 42894 - 블록게임(배열, 구현) c++ 풀이

 

- 6번 매칭점수 문제보다 더 쉬운 문제 같다. 맵의 모든 범위를 블록 사이즈인 2*3, 3*2 범위로 탐색하면서 위에서 블록을 떨궜을 때 직사각형을 만들 수 있는지를 계속 체크해나가는 식으로 문제를 풀었다. 블록 모양이 정해져있어서 추가된 블록 갯수가 2개여야만 직사각형이 만들어지는 조건을 이용해서 쉽게 풀 수 있다. 

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> Board;

bool canFill(int r, int c) { // 행 검사
    for(int i = 0; i < r; ++i) {
        if(Board[i][c] != 0) return false; // 위에 모두 빈칸이여야
    }
    
    return true;
}

bool find(int sr, int sc, int h, int w) {
    int empty = 0;
    int lastBlock = -1;
    for(int i = sr; i < sr + h; ++i) { // 행
        for(int j = sc; j < sc + w; ++j) { // 열
            if(Board[i][j] == 0) {
                if(!canFill(i, j)) return false;
                if(++empty > 2) return false;
            } else {
                if(lastBlock != -1 && lastBlock != Board[i][j]) return false; // 
                lastBlock = Board[i][j];
            }
        }
    }
    
    for(int i = sr; i < sr + h; ++i) {
        for(int j = sc; j < sc + w; ++j) {
            Board[i][j] = 0;
        }
    }
    
    return true;
}

int solution(vector<vector<int>> board) {
    int ans = 0;
    int n = board.size(); // 정사각형
    Board = board;
    
    int cnt = 0;
    do {
        cnt = 0;
        for(int i = 0; i< n; ++i) {
            for(int j = 0; j< n; ++j) {
                if (i <= n - 2 && j <= n - 3 && find(i, j, 2, 3)) ++cnt;
                else if (i <= n - 3 && j <= n - 2 && find(i, j, 3, 2)) ++cnt;
            }
        }
        
        ans += cnt;
    } while(cnt != 0);
    
    return ans;
}

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