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

문제  : Level2 [1차] 프렌즈4블록

 

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

 

[문제 출처] 

 

이 문제는 단순하게 보드를 순회하면서 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다 이 2가지를 구현하면 되는 문제이다

 

밑에 그림과 같이 단순한 4개의 블록은 그냥 지우고 4점을 획득 하면 된다. 

 

 

하지만 다음 그림은 조금은 아주 조금은 복잡하다고 생각 할 수 있지만 전혀 아니다

1번을 바로 지워 버리게 되면 2번에서는 4개를 인식 하지 못하게 되므로 2번에서는 지울 수 가 없다 

즉 4점밖에 획득 하지 못하게 된다

 

지울 경우 단순하게 bool 타입의 체크 배열에다가 표시(true)를 해놓게 되면 2번에서도 지울 수 있게 된다. 

그리고 모든 모든 보드를 순회한 다음 true 로 표시된것을 지우게되면 위에서와 같은 경우도 쉽게 지울 수 있다

 

블록을 아래로 떨어트리는 구현은 보드의 아래부분부터 떨어트리게 구현을 하면 된다.

 

[소스 코드]

 

#include <string>
#include <vector>
#include <cstring>
using namespace std;
const int MAX = 30;
const int dx[] = { 0,0,1,1 };
const int dy[] = { 0,1,1,0 };
bool check[MAX][MAX];
int h, w;
 
int erase(int m, int n, vector<string>& board) {
    int now = 0;
    memset(check, false, sizeof(check));
    for (int i = 0; i < m - 1; i++) {
        for (int j = 0; j < n - 1; j++) {
            if (board[i][j] == ' ') continue;
            if (board[i][j] == board[i][j + 1] &&
                board[i][j] == board[i + 1][j + 1] &&
                board[i][j] == board[i + 1][j]) {
                for (int dir = 0; dir < 4; ++dir) {
                    if (!check[i + dx[dir]][j + dy[dir]]) {
                        now++, check[i + dx[dir]][j + dy[dir]] = true;
                    }
                }
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (check[i][j])board[i][j] = ' ';
        }
    }
    return now;
}
void drop(int m, int n, vector<string>& board) {
    for (int i = m - 2; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == ' ') continue;
            int x = i, y = j;
            while (x + 1 < m && board[x + 1][y] == ' ') {
                board[x + 1][y] = board[x][y], board[x][y] = ' ', x++;
            }
        }
    }
}
int solution(int m, int n, vector<string> board) {
    h = m, w = n;
    int answer = 0;
    while (true) {
        int now = erase(m, n, board);
        if (now == 0) break;
        answer += now;
        drop(m, n, board);
    }
    return answer;
}