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

프로그래머스

 

📄 문제

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

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

 

📝 풀이

#include <string>
#include <vector>
#include <iostream>
#include <set>

using namespace std;

set<pair<int, int>> s;

void removeRect(vector<string>& board, int row, int col)
{
    set<char> m;
    
    m.insert(board[row][col]);
    m.insert(board[row][col + 1]);
    m.insert(board[row + 1][col]);
    m.insert(board[row + 1][col + 1]);
    
    if(m.size() == 1)
    {
        if(m.find('-') != m.end())
            return;
        
        s.insert({row, col});
        s.insert({row, col + 1});
        s.insert({row + 1, col});
        s.insert({row + 1, col + 1});
    }
}

void print(vector<string>& board);

void clearRect(vector<string>& board)
{
    for(pair<int, int> p : s)
        board[p.first][p.second] = '-';
    
    s.clear();
    
    // print(board);
    
    for(int i = 0; i < board[i].size(); ++i)
    {
        for(int j = board.size() - 1; j >= 1; --j)
        {
            if(board[j][i] == '-')
            {
                for(int k = j - 1; k >= 0; --k)
                {
                    if(board[k][i] != '-')
                    {
                        board[j][i] = board[k][i];
                        board[k][i] = '-';
                        break;
                    }
                }
            }
        }
    }
}

void print(vector<string>& board)
{
    for(int i = 0 ; i < board.size(); ++i)
    {
        for(int j = 0; j < board[0].size(); ++j)
        {
            cout<<board[i][j];
        }
        
        cout<<endl;
    }
    
    cout<<endl;
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    
    while(1)
    {
        for(int i = 0; i < m - 1; ++i)
            for(int j = 0; j < n - 1; ++j)
                removeRect(board, i, j);
        
        if(s.empty())
            break;
        
        answer += s.size();
        clearRect(board);
        // print(board);
    }
    
    return answer;
}

• set을 활용하여 문제를 해결하였습니다.
• 매번 2x2 영역이 같은지 removeRect에서 검사합니다. 만약 네 블록이 모두 같은 글자로 되어있다면, set에 삽입합니다. set에 삽입할 때 중복값을 제거할 수 있습니다.
• clearRect에서 글자를 제거한 후, 빈 공간을 위 블록으로 채웁니다.
• 위 과정을 반복하여 set이 비어있을 때(더 이상 2x2가 없음) 종료합니다.