[시뮬레이션] 프렌즈4블록 - 2018 KAKAO BLIND RECRUITMENT

해결 방법

필자는 아래 이미지처럼 2차원 벡터를 이용하여 아래 블록부터 각 열 벡터에 저장했다. 아래 블록부터 저장하면 블록을 삭제하는 과정이 편리하기 때문이다. 또, 블록의 삭제는 화살표의 역방향으로 진행하는게 편리하다.

 

보드를 탐색해나가며 같은 종류의 2x2 블록들을 찾아서 boolean 2차원 배열에 삭제할 블록들을 표시해두고, 나중에 일괄적으로 삭제하는 방법을 이용하면 삭제할 수 있는 블록이 겹치더라도 연산이 간단해진다. 삭제할 수 있는 블록이 겹칠 수 있으므로 같은 종류의 2x2를 발견하자마자 지우는 것은 절대 안된다.

주기마다 삭제한 블록의 개수를 누적시켜주면 문제는 해결된다.

 

 

소스코드

#include <string>
#include <cstring>
#include <vector>
using namespace std;

vector<char> vboard[31];
bool del_board[31][31]; // board에서 삭제할 블록을 표시

// 삭제되는 블록의 수를 반환
int del_cnt() {
    int cnt=0;
    for(int i=0;i<30;i++) for(int j=0;j<30;j++) if(del_board[i][j]) cnt++;
    return cnt;
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    bool check; // 삭제할 수 있는 블록이 있는지 확인
    for(int i=m-1;i>=0;i--) for(int j=0;j<n;j++) vboard[j].push_back(board[i][j]);
    do {
        memset(del_board, false, sizeof(del_board));
        check=false;
        for(int i=0;i<n-1;i++){
            for(int j=0;j<vboard[i].size();j++){
                char base = vboard[i][j]; // 블록의 종류
                if(j>=(int)vboard[i].size()-1) break;
                if(j>=(int)vboard[i+1].size()-1) break;
                if(vboard[i][j+1]==base&&vboard[i+1][j]==base&&vboard[i+1][j+1]==base){
                    check=true;
                    del_board[i][j]=true;
                    del_board[i][j+1]=true;
                    del_board[i+1][j]=true;
                    del_board[i+1][j+1]=true;
                }
            }
        }
        for(int i=0;i<n;i++){
            int vsize=vboard[i].size();
            for(int j=vsize-1;j>=0;j--){
                // 블록 삭제
                if(del_board[i][j]) vboard[i].erase(vboard[i].begin()+j, vboard[i].begin()+j+1);
            }
        }
        answer+=del_cnt();
    } while(check);
    return answer;
}

 

테스트케이스 11개 모두 정답

 

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/17679