[프로그래머스] [1차] 프렌즈4블록 C++ 풀이 및 해설

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

프로그래머스

 

풀이 방법

1. 동일한 2x2 블록을 찾는다. - check

2. 동일한 2x2 블럭을 저장해 놨다가 한 번에 삭제한다. - remove

3. 삭제로인해 생긴 빈 공간을 메꾼다. - move

 

check는 좌측 위에서 우측 아래 방향으로 검사하면 편하고

빈 공간을 메꾸는 것은 우측 아래에서 좌측 위 방향으로 검사하면 스택(테트리스)과 같이

블록들이 빈 공간을 통해 뚝뚝 떨어지는 기능을 구현할 수 있다.

 

check(i,j) : 좌표 (i,j)를 기준으로 우측, 아래측, 우측 아래(대각선) 블록이 동일한지 검사하여 boolean 반환

remove(i,j) :  check()를 통해 삭제할 블록을 저장 -> 블록 삭제('X'로 변환) -> 삭제할 블록 개수 반환

move :  맨 우측 아래부터 좌측 방향으로 탐색하며 'X'를 만날경우 그 위의 'X'가 아닌 블럭(카카오 블록)과 교환

 

전체 코드

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

bool check(int i, int j, vector<string>& board) {
    
    char c = board[i][j]; // 현재 위치 문자 저장
    if(c!='X' &&board[i][j+1] == c && board[i+1][j] == c
       && board[i+1][j+1] == c) // 현재 문자와 동일한 2x2라면
        return true;
    else
        return false;
}

int remove(int m, int n, vector<string>& board) {
    
    map<pair<int, int>, bool> ma; // 삭제할 좌표 저장
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            if(i+1<m && j+1<n && check(i,j, board)) { // 2x2 동일하다면 삭제 좌표 추가
                ma.insert({make_pair(i,j), true});
                ma.insert({make_pair(i,j+1), true});
                ma.insert({make_pair(i+1,j), true});
                ma.insert({make_pair(i+1,j+1), true});
            }
        }
    }
    
    // 저장된 좌표들로 삭제 - 'X' 변환
    for(auto iter = ma.begin(); iter!=ma.end(); iter++) {
        board[iter->first.first][iter->first.second] = 'X';
    }
    
    return ma.size(); // 삭제된(할) 좌표의 개수 반환
}

void move(int m, int n, vector<string>& board) {
    
    for(int i=m-1; i>=0; i--) {
        for(int j=n-1; j>=0 ;j--) {
            if(board[i][j]=='X') { // 'X' 발견
                int y = i; // 위로 이동을 위해 y에 저장
                while(y>=0) { // 범위를 벗어날때까지
                    if(board[y][j]!='X') { // 'X가 아닌 문자 발견시 교환
                        board[i][j] = board[y][j];
                        board[y][j] = 'X';
                        break;
                    } else { // 'X' 문자라면 위로 이동
                        y--;
                    }
                }
            }
        }
    }
    
    
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    
    int eraseCnt; // 삭제할 블록 개수
    while(1) {
        eraseCnt=remove(m, n, board); // 이번에 삭제할 블록 개수 갱신
        if(eraseCnt!=0) { // 삭제할 블록이 존재한다면
            answer+=eraseCnt; // answer에 추가하고
            move(m, n, board); // 빈자리 메꾸기위해 블록 이동
        } else {
            break;
        }
    }
    return answer;
}