[Programmers] Level2 : [1차] 프렌즈4블록

Question

---

Solution

• 다음과 같은 단계를 반복시켜야 한다.
  1. 2x2 블록 찾기
  2. 블록 제거
  3. 빈 공간 채우기
• 위 단계를 while 루프로 하되 더 이상 제거할 블록이 없다면 중단한다.
• 2x2 블록의 경우 n-1, m-1 까지 2x2형태의 문자들이 모두 같은지 확인하면 된다.
• 2x2 블록을 찾으면 vector에 해당 시작 idx를 넣는다.
• 블록 제거 단계에서 vector에 저장된 idx를 꺼내 2x2형태로 ‘0’ 초기화 시키되
  겹치는 영역을 고려하여 이미 ‘0’으로 초기화 되어 있으면 answer를 증가시키지 않는다.
  1. 이차원 배열에서 밑에서부터 빈 블록을 확인하고 column은 같고 row만 감소시켜 빈 블록이 아닌 것을 찾으면 땡겨온다.

---

Cord

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<string> board)
{
    int answer = 0;

    while (true)
    {
        vector<pair<int, int>> clearIdx; // 제거할 블록의 idx

        // 2x2 블록 찾기
        for (int row = 0; row < m - 1; ++row)
        {
            for (int column = 0; column < n - 1; ++column)
            {
                if (board[row][column] != '0' &&
                    board[row][column] == board[row][column + 1] &&
                    board[row][column] == board[row + 1][column] &&
                    board[row][column] == board[row + 1][column + 1])
                { clearIdx.push_back({ row, column }); }
            }
        }

        if (clearIdx.empty()) { break; }    // 제거할 블록이 없으니 빠져나오기

        // 블록 제거
        for (int i = 0; i < clearIdx.size(); ++i)
        {
            pair<int, int> temp = clearIdx[i];

            if (board[temp.first][temp.second] != '0') 
            { 
                board[temp.first][temp.second] = '0';
                ++answer; 
            }
            if (board[temp.first][temp.second + 1] != '0')
            {
                board[temp.first][temp.second + 1] = '0';
                ++answer;
            }
            if (board[temp.first + 1][temp.second] != '0')
            {
                board[temp.first + 1][temp.second] = '0';
                ++answer;
            }
            if (board[temp.first + 1][temp.second + 1] != '0')
            {
                board[temp.first + 1][temp.second + 1] = '0';
                ++answer;
            }
        }

        // 빈 공간 채우기
        for (int row = m - 1; row > 0; --row)
        {
            for (int column = n - 1; column >= 0; --column)
            {
                if (board[row][column] == '0')
                {
                    for (int height = row-1; height >= 0; --height)
                    {
                        if (board[height][column] != '0')
                        {
                            board[row][column] = board[height][column];
                            board[height][column] = '0';
                            break;
                        }
                    }
                }
            }
        }
    }

    return answer;
}

---

Result