[c++] 프로그래머스 - 프렌즈4블록

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

[프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/17679)

풀이

• 블록 퍼즐 게임 문제이다
• 생각보다 특별한 알고리즘이 필요하진 않았다
• 문제에서 요구한 대로 구현하다보면 정답이 나온다

주의할점

• 이 경우처럼 2x2블록이 겹쳐있는 경우 바로 삭제를 해버리면, 오른쪽 밑의 세 블록은 사라지지 않는 판정이 되므로 주의한다.

풀이

int dx[3] = {1, 0, 1};
int dy[3] = {0, 1, 1};

bool check(int x, int y, vector<string> &board) {
    for(int i=0; i<3; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx < 0 || ny < 0 || nx >= N || ny >= M) return false;
        if(board[x][y] != board[nx][ny]) return false;
    }
    return true;
}

• 이 함수를 통해 2x2 블록인지 아닌지 체크한다

int Remove(vector<pair<int, int>> &v, vector<string> &board) {
    int cnt = 0;
    for(auto &p : v) {
        int x = p.first;
        int y = p.second;
        if(board[x][y] != '-') {
            board[x][y] = '-';
            cnt++;
        }
    }
    return cnt;
}

void DropBlocks(vector<string> &board) {
    for(int j=0; j<M; j++) {
        for(int i=N-1; i>=0; i--) {
            if(board[i][j] == '-') {
                for(int k=i-1; k>=0; k--) {
                    if(board[k][j] != '-') {
                        swap(board[i][j], board[k][j]);
                        break;
                    }
                }
            }
        }
    }
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    bool canRemoveMore = true;
    N = m; M = n;
    
    do {
        canRemoveMore = false;
        vector<pair<int, int>> nextRemove;
        for(int i=0; i<m-1; i++) {
            for(int j=0; j<n-1; j++) {
                if(board[i][j] != '-' && check(i, j, board)) {
                    nextRemove.emplace_back(i, j);
                    nextRemove.emplace_back(i, j+1);
                    nextRemove.emplace_back(i+1, j);
                    nextRemove.emplace_back(i+1, j+1);
                }
            }
        }
        if(nextRemove.size() > 0) canRemoveMore = true;
        answer += Remove(nextRemove, board);
        DropBlocks(board);
    } while(canRemoveMore);
    
    return answer;
}

• 모든 칸에 대해서 체크 - 삭제 - 드롭을 반복하면서, 더이상 삭제가 안될 때 까지 반복한다.
• 겹친 사각형을 처리하기 위해 바로 삭제가 아닌, vector에 따로 저장해두었다가 삭제하는 방식으로 처리했다.
• 해당 vector가 비어있다면, 더이상 삭제할 블록이 없는 것이므로 반복문을 탈출한다.

전체 코드

#include <string>
#include <vector>

using namespace std;

int N, M;
int dx[3] = {1, 0, 1};
int dy[3] = {0, 1, 1};

bool check(int x, int y, vector<string> &board) {
    for(int i=0; i<3; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx < 0 || ny < 0 || nx >= N || ny >= M) return false;
        if(board[x][y] != board[nx][ny]) return false;
    }
    return true;
}

int Remove(vector<pair<int, int>> &v, vector<string> &board) {
    int cnt = 0;
    for(auto &p : v) {
        int x = p.first;
        int y = p.second;
        if(board[x][y] != '-') {
            board[x][y] = '-';
            cnt++;
        }
    }
    return cnt;
}

void DropBlocks(vector<string> &board) {
    for(int j=0; j<M; j++) {
        for(int i=N-1; i>=0; i--) {
            if(board[i][j] == '-') {
                for(int k=i-1; k>=0; k--) {
                    if(board[k][j] != '-') {
                        swap(board[i][j], board[k][j]);
                        break;
                    }
                }
            }
        }
    }
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    bool canRemoveMore = true;
    N = m; M = n;
    
    do {
        canRemoveMore = false;
        vector<pair<int, int>> nextRemove;
        for(int i=0; i<m-1; i++) {
            for(int j=0; j<n-1; j++) {
                if(board[i][j] != '-' && check(i, j, board)) {
                    nextRemove.emplace_back(i, j);
                    nextRemove.emplace_back(i, j+1);
                    nextRemove.emplace_back(i+1, j);
                    nextRemove.emplace_back(i+1, j+1);
                }
            }
        }
        if(nextRemove.size() > 0) canRemoveMore = true;
        answer += Remove(nextRemove, board);
        DropBlocks(board);
    } while(canRemoveMore);
    
    return answer;
}