[2018 1차 KAKAO] 프렌즈4블록

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

코딩테스트 연습 - [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;
    
    while(true){
        vector<vector<bool>> score(m, vector<bool>(n, false));
        int cnt = 0;
        
        for(int i=0; i<m-1; i++){
            for(int j=0; j<n-1; j++){
                char target = board[i][j];
                if(target == '#') continue;
                if(board[i][j+1] == target && board[i+1][j] == target && board[i+1][j+1] == target){
                    score[i][j] = true;
                    score[i][j+1] = true;
                    score[i+1][j] = true;
                    score[i+1][j+1] = true;
                    cnt++;
                }
            }
        }
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(score[i][j]){
                    answer++;
                }
            }
        }
        
        if(cnt == 0) break;
        
        for(int i=0; i<n; i++){
            queue<char> q;
            for(int j=m-1; j>=0; j--){
                if(!score[j][i]){
                    q.push(board[j][i]);
                }
            }
            
            for(int j=m-1; j>=0; j--){
                if (q.empty())
                    board[j][i] = '#';
                else {
                    board[j][i] = q.front();
                    q.pop();
                }
            }
        }
    }
    return answer;
}