프로그래머스 (2017년)KAKAO BLIND RECRUITMENT 프렌즈4블록 c++

https://programmers.co.kr/learn/courses/30/lessons/17679

코딩테스트 연습 - [1차] 프렌즈4블록 | 프로그래머스

백준의 Puyo Puyo문제나 SWEA의 벽돌 깨기 문제와 비슷한 문제다.

이 문제에서는 네 칸만 확인해주면 되므로 모든 (i, j) 칸이 바로 오른쪽(j+1, i), 바로 아래쪽(i+1, j), 대각선 아래(i+1, j+1)와 같은지 확인해주면 된다. 이때 범위를 넘어가지 않도록 i는 m-1보다 작을 때까지, j는 n-1보다 작을 때까지만 검사한다. 그리고 지워진 칸에 대해서는 검사하지 않는다.

 

 

네 칸이 모두 같을 때, 해당 칸이 이미 다른 칸으로부터 지워질 수도 있기 때문에 바로 answer값을 증가시키지 않는다. 위의 그림에서 라이언 하나가 중복되어 있는 경우다. check배열을 사용하여 false인 경우에만 answer값을 증가시킨고 check배열의 값을 true로 바꿔준다.

 

 

모든 칸에 대해서 검사를 하는동안 한 번이라도 지워지는 게 있다면 flag변수가 true값을 갖는다.

검사가 끝난 후에 flag변수가 false값을 가지고 있다면 지워지는 게 없다는 뜻이므로 검사를 종료한다.

true값을 가지고 있다면 지워져야하는 블록들이 있다는 뜻이므로 check배열의 값이 true인 블록들을 빈칸으로 만드어준다.

 

 

지워진 블록들이 있다면 이제 떠있는 블록들을 아래로 내려줘야한다.

모든 열에 대해서 각 행들을 밑에서부터 검사해준다. 밑에서부터 빈칸을 찾은 후에 그 빈칸보다 위쪽에 떠있는 블록을 찾아서 해당 빈칸으로 내려주면 된다. ok변수를 사용해서 발견한 빈칸보다 위쪽 칸들이 모두 빈칸일 경우에는 떠있는 블록이 없다는 뜻이므로 다음 열의 검사로 넘어간다.

 

 

#include <string>
#include <vector>
#include <cstring>
 
using namespace std;
 
bool check[30][30];
 
int solution(int m, int n, vector<string> board) {
    int answer = 0;
 
    while (true) {
 
        bool flag = false;
        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]) continue;
                if (board[i][j] != board[i + 1][j]) continue;
                if (board[i][j] != board[i + 1][j + 1]) continue;
 
                flag = true;
 
                if (!check[i][j]) {
                    check[i][j] = true;
                    answer++;
                }
 
                if (!check[i][j + 1]) {
                    check[i][j + 1] = true;
                    answer++;
                }
 
                if (!check[i + 1][j]) {
                    check[i + 1][j] = true;
                    answer++;
                }
 
                if (!check[i + 1][j + 1]) {
                    check[i + 1][j + 1] = true;
                    answer++;
                }
 
 
 
            }
        }
 
 
        //더 지워질게 없다면 종료
        if (!flag) break;
 
 
        //붙어있는 애들 지워준다.
        for (int i = 0; i<m; i++) {
            for (int j = 0; j<n; j++) {
                if (check[i][j]) board[i][j] = ' ';
            }
        }
 
 
        //블록 지워진 후에 아래로 떨어져서 빈공간 채운다.
        for (int j = 0; j<n; j++) {
            for (int i = m - 1; i >= 0; i--) {
                if (board[i][j] != ' ') continue;
 
                bool ok = false;
 
                for (int k = i - 1; k >= 0; k--) {
 
                    if (board[k][j] != ' ') {
                        board[i][j] = board[k][j];
                        board[k][j] = ' ';
                        ok = true;
                        break;
                    }
 
                }
 
                if (!ok) break;
 
            }
        }
 
 
    }
    return answer;
}