[2019 KAKAO BLIND RECRUITMENT] 블록 게임

 

블록 위치를 따로 저장하고 여러 번 돌리는 게 효율적일 거 같아서 시도하였으나 매우 번거로워 방법을 바꾸고 이 방법으로 풀었다.

 

풀이 과정

풀면서 고려했던 사항

1. 채울수 있는지 체크하는 방법 구현 -> 위에서 쭉 내려보며 0이 아닌 게 있는지 체크한다. 있으면 채울 수 없다.

2. 하지만 가리던 게 지워져서 원래는 못 채우던걸 채울 수 있다. -> 여러 번 돌려서 지운 게 없을 때까지 돌린다.

소스코드

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
 
int N;
vector<vector<int>> Board;
 
bool canFill(int row, int col) {
    for (int i = 0; i < row; i++) {
        if (Board[i][col] != 0)
            return false;
    }
    return true;
}
 
bool find(int row, int col, int h, int w) {
    int empty_cnt = 0;
    int block_num = -1;
    for (int r = row; r < row + h; r++) {
        for (int c = col; c < col + w; c++) {
            if (Board[r][c] == 0) {
                if (!canFill(r, c))
                    return false;
                empty_cnt++;
                if (empty_cnt > 2)
                    return false;
            }
            else {
                if (block_num != -1 && block_num != Board[r][c]) {//서로다른블록으로 엮인경우
                    return false;
                }
                block_num = Board[r][c];//업데이트
            }
        }
    }
    for (int r = row; r < row + h; r++) {
        for (int c = col; c < col + w; c++) {
            Board[r][c] = 0;
        }
    }
    return true;
}
 
int solution(vector<vector<int>> board) {
    int answer = 0;
    Board = board;
    N = board.size();
    int cnt;
 
    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++;
                }
            }
        }
        answer += cnt;
    } while (cnt);
 
    return answer;
}

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42894