프렌즈4블록 (프로그래머스) - C++

코딩테스트 연습 - [1차] 프렌즈4블록

• 문제
  • 입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

• 설명

• 풀이
  • 위에서부터 체크하면서 오른쪽, 아래, 대각선을 체크하여 2*2 의 값이 모두 같다면 set에 해당 인덱스를 추가한다.
  • set를 사용하는 이유는 중복이 있을 수 있기 때문이다.
  • 다 체크를 한 뒤에 지워지는 블록들을 '#'으로 변경해준다.
  • 바닥 바로 위 칸부터 올라오면서 아래 빈 공간(#)이 있는지 확인한다.
  • 있다면 계속 아래로 확인하면서 블럭의 값과 #을 바꿔준다.(한칸씩 내려가는 것을 구현한 것)
  • 바닥 또는 더이상 빈 공간이 아닐 경우 멈춘다.
  • 위 과정을 반복하며 더이상 지워지는 블럭이 없을 경우 종료한다.

#include <string>
#include <vector>
#include <utility>
#include <set>
#include <iostream>
 
using namespace std;
 
int solution(int m, int n, vector<string> board) {
    int answer = 0;
    
    set<pair<int,int>> clear;
    //m은 세로 n은 가로 
    //board는 길이가 n인 문자열 배열 m개
    
    //2*2 모양이 되면 사라짐
    //블럭이 아래로 떨어짐
    
    //RMAFNTJC
    do{
        clear.clear();//set 초기화
        
        for(int i = 0 ; i < m-1 ; i++)
        {
            for(int j = 0 ; j < n-1 ; j++)//빈 공간이 아닌 블럭 중 2*2형태의 블럭인 경우 set에 추가한다.
            {
                if(board[i][j] != '#' &&
                   board[i][j] == board[i+1][j] && 
                   board[i][j] == board[i][j+1] && 
                   board[i][j] == board[i+1][j+1])
                {
                    cout << i <<"," <<j << " ";
                    clear.insert(make_pair(i,j));
                    clear.insert(make_pair(i+1,j));
                    clear.insert(make_pair(i,j+1));
                    clear.insert(make_pair(i+1,j+1));
 
                    //리스트에 저장?
                }
            }
        }
    
       
        for(auto const &var : clear)//지워지는 블럭을 #으로 변경해준다.
        {
            
            int x = var.first;
            int y = var.second;
            board[x][y] = '#';
 
            answer++;
        }
   
 
        for(int i = m-2 ; i >= 0 ; i--)
        { 
            
            for(int j = 0 ; j < n ; j++)
            {
                int height = i;
                while(height < m-1 && board[height+1][j] == '#')//아래로 내려가면서 블럭의 값을 빈 공간에 넣어준다.
                {
                        
                        board[height+1][j] = board[height][j];
                        board[height][j] = '#';
                        height++;
                }
                    
                    
                
            }
        }
 
        
    }while(!clear.empty());//더 이상 제거되는 블럭이 없을 때 까지 반복한다.
    
    
    return answer;
}