[프로그래머스] 2018 KAKAO BLIND RECRUITMENT - [1차] 프렌즈4블록, C++

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

코딩테스트 연습 - [1차] 프렌즈4블록 | 프로그래머스

 본 문제는 '2018 KAKAO BLIND RECRUITMENT'로 kakao Tech에 의하면 "정답률48.01%"이다. 난이도는 상으로 구분되어 있다.

2x2의 크기에 블록이 만약 같은 블록이면 없어지고, 위에 있는 블록이 밑으로 내려오게 하는 문제다. 개인적으로 백준 SW 역량 테스트 준비 - 문제 (시뮬레이션)에 있는 '미네랄'과 유사하다고 생각한다. 하지만 미네랄에서는 밑으로 내려올 때, 미네랄 덩어리가 내려오기 때문에 미네랄 문제가 [1차] 프렌즈4블록의 문제보다 까다롭다고 생각한다.

https://www.acmicpc.net/problem/2933

2933번: 미네랄

 참고로 [1차] 프렌즈4블록을 풀 때, 위에서 밑으로 빈 공간으로 블록이 내려올 때, 빈 공간만큼 한번에 내려오게 코딩하고 싶었지만, 구현하다 안되서 포기하고 한 칸씩 내려가도록 구현했다. 다음에 다시 구현해봐야겠다.

#include <string>
#include <vector>
#include <iostream>
#include <queue>
 
using namespace std;
 
int solution(int m, int n, vector<string> board) {
    int answer = 0;
    bool chk;
    queue<pair<int, int>> q;
    do {
        chk = true;
        for (int i = 0; i < m-1; i++) {
            for (int j = 0; j < n-1; j++) {
                char tmp = board[i][j];
                if (tmp == '0') continue;
                // 2x2 블록 탐색
                if (tmp == board[i+1][j] && tmp == board[i][j+1] && tmp == board[i+1][j+1]) {
                    chk = false;
                    q.push(make_pair(i, j));
                    q.push(make_pair(i+1, j));
                    q.push(make_pair(i, j+1));
                    q.push(make_pair(i+1, j+1));
                }
            }
        }
        // 블록 지우기
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            board[x][y] = '0';
        }
        bool is_true;
        // 위에서 밑으로 빈 공간으로 한 칸씩 블록 내리기
        do {
            is_true = true;
            for (int j = 0; j < n; j++) {
                for (int i = 0; i < m-1; i++) {
                    if (board[i][j] != '0' && board[i+1][j] == '0') {
                        is_true = false;
                        board[i+1][j] = board[i][j];
                        board[i][j] = '0';
                    }
                }
            }
        } while (!is_true);
    } while (!chk);
    // 빈 공간 개수 cnt
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == '0') answer += 1;
        }
    }
    // 블록 이동 결과 출력
    /*
    for (int i = 0 ; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cout << board[i][j];
        }
        cout << "\n";
    }
    */
    return answer;
}