[프로그래머스] [1차] 프렌즈4블록

문제 설명

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 프렌즈4블록. 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.
/* 중략 */
입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

제한사항

• 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
• 2 ≦ n, m ≦ 30
• board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

---

풀이

25분

2x2 지울 공간 탐색 -> 없으면 종료하고, 있으면 지운 뒤 떨어뜨림 -> 반복 

의 과정을 구현하였다. 예시에서 2x2 공간의 모서리가 겹치는 예시를 잘 보여주었기 때문에, 예외처리에서 실수 없이 구현할 수 있었던 것 같다.

코드

// 10:40 ~ 11:06
#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

int solution(int m, int n, vector<string> board) {
    int cnt = 0;
    queue<pair<int,int>> q;
    vector<char> col;
    int x,y;
    
    while(true){
        for(int i =0; i + 1 < m; ++i){
            for(int j =0; j + 1 < n; ++j){
                if(board[i][j] == ' ') continue;
                if(board[i][j] == board[i + 1][j] && board[i][j + 1] == board[i + 1][j + 1] && board[i][j] == board[i + 1][j + 1]){
                    q.push(make_pair(i,j));
                }
            }
        }
        if(q.empty()) break;
        while(!q.empty()){
            x = q.front().first;
            y = q.front().second;
            q.pop();
            
            if(board[x][y] != ' '){
                board[x][y] = ' ';
                ++cnt;
            }
            if(board[x + 1][y] != ' '){
                board[x + 1][y] = ' ';
                ++cnt;
            }
            if(board[x][y + 1] != ' '){
                board[x][y + 1] = ' ';
                ++cnt;
            }
            if(board[x + 1][y + 1] != ' '){
                board[x + 1][y + 1] = ' ';
                ++cnt;
            }
        }
        
        for(int j = 0; j < n; ++j){
            col.clear();
            for(int i = 0; i < m; ++i){
                if(board[i][j] != ' ') col.push_back(board[i][j]);
            }
            while(col.size() < m) col.insert(col.begin(),' ');
            for(int i = 0; i < m; ++i){
                board[i][j] = col[i];
            }
        }
    }
    return cnt;
}