[프로그래머스] 프렌즈4블록 (level2, c++)

 

문제

---

같은 모양의 카카오프렌즈 블록이 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)을 의미한다

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

 

문제조건

---

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

 

풀이

---

보드를 돌며 2*2를 만족하는 블록들이 있는지를 확인해 주었다. 지워지는 문자들이 겹치는 경우가 있을 수 있으므로 바로 지우지 않고, 지울 것들을 체크해 주었다. 이후 체크된 것을 'X'로 표시하여 지워주었다. 지울 것이 없는 경우 게임이 끝난 것이기 때문에 종료 조건으로 사용하였다.

블록을 지운 이후 블록을 옮길 수 있다면 옮겨 주어야 한다. 이때 다음과 같은 예시를 생각해보면 좋다.

AA
BB
ZZ
ZZ
CC

처음에는 한 블록 기준으로 아래에 빈 공간이 있다면 옮겨주는 식으로 함수를 만들어주었다. 하지만 그렇게 한다면 옮긴 후 또 옮길 수 있음에도 블록들이 옮겨지지 않았다. 이를 해결하기 위해 빈 블록을 기준으로 위에 블록들이 있다면 옮겨주도록 변경하였다.

 

코드

---

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
int mm, nn;
vector<string> b;
bool check[31][31];
int ANS = 0;
 
void move(int x, int y){
   
    if (b[x][y] == 'X') { // 내가 빈 공간이라면
        for (int k = x; k > 0; k--) {
            if (b[k - 1][y] == 'X') break;
            b[k][y] = b[k - 1][y]; // 위에 있는 것을 땡겨옴
            b[k - 1][y] = 'X'; // 땡겨진 것들의 원래 자리를 빈공간으로
        }
    }
}
 
bool eraseBoard(){
    bool c = false;
    for(int i=0; i<mm; i++){
        for(int j=0; j<nn; j++){
            if(check[i][j]){
                ANS++;
                b[i][j] = 'X';
                c = true;
            }
        }
    }
    
    return c;
}
 
void find(int x, int y){
    int dx[3] = {1, 0, 1};
    int dy[3] = {0, 1, 1};
    
    int p = b[x][y];
    int cnt = 1;
    if(p!='X'){
        for(int i=0; i<3; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx>=0&&nx<mm&&ny>=0&&ny<nn&&b[nx][ny]!='X'){
                if(b[nx][ny]==p) cnt++;
            }
        }
    }
    
    
    //지워질 조건 만족 -> 지우기로 check
    if(cnt==4){
        check[x][y] = true;
        for(int i=0; i<3; i++){
            check[x + dx[i]][y + dy[i]] = true;
        }
    }
}
 
int solution(int m, int n, vector<string> board) {
    mm = m;
    nn = n;
    b = board;
 
    while(1){
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                find(i, j);
            }
        }
        
    
        if(eraseBoard()){          
            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    move(i, j);
                }
            }  
        }
        
    
        else break;
        
        // 초기화
        for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    check[i][j]=false;
                }
        }   
          
    }
    
    return ANS;
}