C++:: 프로그래머스 < [1차] 프렌즈4블록 >

풀고나니 크게 어렵지 않은 문제이지만 처음에 시간초과와 문제에 대한 접근을 잘못하여 애를 많이 먹은 문제이다.
첫번째로 했던 수는 전체 board에서 블록을 맞추었을때 바로 없애주고 내려준 부분이다. 이와 같이 하게되면 안되고 먼저 보드에서 해당 블록들을 전부 없애준다음 다같이 내려주어야한다. 순서의 차이이지만 나오는 결과는 전혀 다를 수 있기 때문에 이부분을 주의해야한다.
두번째로 했던 실수는 코드를 구현할때 2x2배열을 판별하는 부분에서 재귀적 접근을 했다가 시간초과가 난 부분이다. 30 x 30 크기의 보드일때 시간초과가 발생하기 때문에 방문 배열을 따로 구현해서 판별하는 방식으로 코드를 수정하였다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

void fillEmpty(int m, int n, vector<string>& board) {// 빈공간 내려주는 함수
    for (int j=0; j<n; j++) {
        string tmp = "";
        for (int i=m-1;i>=0;i--) if (board[i][j] != ' ') tmp += board[i][j];// 밑에서 부터 거꾸로 들어있는 블록 저장
        int i = m-1;
        for (auto c : tmp) board[i--][j] = c;// 밑에서 부터 채워주고
        for (; i>=0; i--) board[i][j] = ' ';// 윗부분은 공백으로 채워준다.
    }
}

bool is_hit(int i, int j, vector<string>& board, vector<vector<bool>>& vis) {
    if (board[i][j] != board[i+1][j] ||
        board[i][j] != board[i][j+1] ||
        board[i][j] != board[i+1][j+1]) return false ;// 적합하지 않다면
    vis[i][j] = true;
    vis[i+1][j] = true;
    vis[i][j+1] = true;
    vis[i+1][j+1] = true;
    return true;
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    vector<vector<bool>> vis(m, vector<bool>(n, false));
    
    while (1) {
        bool done = true ;
        fill(vis.begin(), vis.end(), vector<bool>(n, false));// 방문 배열 초기화
        for (int i=0; i<m-1; i++) {
            for (int j=0; j<n-1; j++) {
            	// 공백이 아니고 조건에 부합한다면 사각형부분을 방문체크해주고 끝나지 않았음으로 플래그를 바꿔준다.
                if (board[i][j] != ' ' && is_hit(i, j, board, vis)) done = false;
            }
        }
        if (done) break;// 더이상 부합하는 사각형이 없다면
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (vis[i][j]) board[i][j] = ' ';// 조건에 부합하는 부분들 전부 공백으로 바꿔준다.
            }
        }
        fillEmpty(m, n, board);// 빈공간 내려주기
    }
    for (auto s : board) {
        for (auto c : s) if (c == ' ') answer++;
    }
    return answer;
}