Programmers : 프렌즈4블록

풀이요약

구현, 완전탐색

풀이상세

1. 유사 BFS 이다. 현재 인덱스에서 오른쪽, 아래, 대각선 블록을 보고 현재 인덱스의 블록과 동일한 경우면 블록은 폭발한다.

2. 단, 연속 폭발을 통해 중복해서 폭발하는 구간이 생길 수 있으므로, 바로 폭발시키는 것이 아닌 현재 탐색이 모두 종료된 이후 폭발시킨다.

3. 폭발시킨 블록은 0 으로 표기하였다. 0 이 동일하여 판단하는 경우가 생길 수 있으므로, 현재 블럭이 0 이라면 바꾸자.

4. 현재 페이즈에서 모든 폭발을 끝내고 0 구간과 상위 떠있는 블록을 스왑한다. 단, 0 이 연이어 있을 수 있으니, 0 아래의 부분을 계속 탐색하여, 가장 아래의 0 과 스왑되도록 하자.

5. 정답은 없어진 블록을 갯수를 구하는 문제이다. 빠른 계산을 위해 폭발시 갯수를 세도록 했다. (단, 중복되는 부분이 존재할 수 있으므로, 이미 0 이 된 곳은 제외하여 세도록 했다.)

#include <string>
#include <vector>
using namespace std;
vector<pair<int,int>> tmp;
int solution(int m, int n, vector<string> board) {
    int answer = 0;
    // 모두 탐색 
    while(true) {
        bool check = false;
        tmp.clear();
        for(int i=0; i<board.size(); i++) {
            for(int j=0; j<board[i].size(); j++) {
                if(i+1>=m || j+1>=n) continue;
                if(board[i][j] == '0') continue;
								// 현재 인덱스에서 오른쪽, 아래, 대각선 아래 보고 모두 같다면 좌표저장
                if(board[i][j] == board[i+1][j] && board[i+1][j] == board[i][j+1] && board[i][j+1] == board[i+1][j+1]) {
                    check = true;
                    tmp.push_back({i,j}), tmp.push_back({i+1,j}), tmp.push_back({i,j+1}), tmp.push_back({i+1,j+1});
                }
            }
        }
        if(!check) break;
        
        // 탐색 후 저장한 좌표들 비우기
        for(auto p : tmp) {
            if(board[p.first][p.second] == '0') continue;
            board[p.first][p.second] = '0';
            answer++;
        }
        
        
        // 아래에서 위로 거꾸로 보면서 빈공간 있으면 한칸씩 내리기
        for(int i=board.size()-2; i>=0; i--) {
            for(int j=0; j<board[i].size(); j++) {
                if(board[i][j] != '0' && board[i+1][j] == '0') {
                    int idx = i+1;
                    while(idx+1<m && board[idx+1][j] == '0') idx++;
                    int t = board[i][j];
                    board[i][j] = board[idx][j];
                    board[idx][j] = t;
                }
            }
        }
    }

    return answer;
}