프로그래머스/lv2/17679.［1차］프렌즈4블록 2018 KAKAO BLIND RECRUITMENT

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int m, int n, vector<string> v) {
    int answer = 0, sign;
    queue<pair<int, int>> t;

    while (1) {
        sign = 0;
        for (int i = 0; i < m - 1; i++) {
            for (int j = 0; j < n - 1; j++) {
                if (v[i][j] != ' ' && v[i][j] == v[i][j + 1] && v[i][j] == v[i + 1][j] && v[i][j] == v[i + 1][j + 1]) {
                    t.push({i, j});
                    sign = 1;
                }
            }
        }

        if (!sign) break;
        vector<vector<int>> visited(m, vector<int>(n, 0));

        while (!t.empty()) {
            auto i = t.front();
            t.pop();
            int x = i.first, y = i.second;
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    if (!visited[x + i][y + j]) {
                        v[x + i][y + j] = ' ';
                        visited[x + i][y + j]++;
                        answer++;
                    }
                }
            }
        }

        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (v[i + 1][j] == ' ' && v[i][j] != ' ') {
                    int x = i + 1;
                    char temp = v[i][j];
                    v[i][j] = ' ';
                    while (x + 1 < m && v[x + 1][j] == ' ') x++;
                    v[x][j] = temp;
                }
            }
        }
    }

    return answer;
}

사각형 기준 왼쪽 위부터 검사해 4개의 블록이 같으면 pair형태로 Queue에 좌표를 저장해준다.
Queue에 저장한 좌표를 기준으로 오른쪽, 아래, 오른쪽 아래를 빈칸으로 바꾼다.
몇개의 블록이 빈칸으로 변환됐는지 알아야하기에 visited로 체크하며 answer의 수를 올린다.

그리고 게임판 오른쪽 아래 끝부터 시작하여 각 블록을 밑으로 내린다.
오른쪽 아래 끝부터 시작하는 이유는 왼쪽 위부터 블록을 내린다면, 내려간 블록의 위쪽 블록들 또한 내려주어야 하는데,
그 과정이 오른쪽 아래 끝부터 시작하는 로직에 비해 번거롭기 때문이다.

위 과정을 반복하며 정사각형 형태로 4개의 블록이 뭉치지 않았다면 반복문을 종료한다.