[Programmers] 프렌즈4블록

처음 그림에서 몇개의 그림이 지워지는지 구하는 문제이다.

문제해결 전략
보드의 최대 크기가 30x30으로 크지 않기도 하고 확인할 부분이 좌 우 대각선 총 세 방향 뿐이므로 전체를 탐색해도 반복횟수가 그리 크지 않다.

모든 좌표에서 세 방향을 확인하여 모두 일치하면 임시 보드를 1로 세팅한 후 1의 갯수를 세면 된다.

그리고 블록 재배치 과정은 그냥 아래에서부터 올라가면서 처음으로 비어있지 않은 블록을 만나면 두 위치를 스왑해 주고, 이 과정을 모든 칸에 대하여 실행하면 된다.

코드

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<string> board) {
    int answer;
    int cnt = 0;
    while(1){
        vector<vector<int>> v;
        int flag = 0;
        for(int i=0;i<m;i++){
            vector<int> tmp;
            for(int j=0;j<n;j++){
                tmp.push_back(0);
            }
            v.push_back(tmp);
        }    
        
        for(int i=0;i<m-1;i++){
            for(int j=0;j<n-1;j++){
                char c = board[i][j];
                if(c == 'x')
                    continue;
                if((c==board[i+1][j])&&(c==board[i][j+1])&&(c==board[i+1][j+1])){
                    v[i][j] = 1;
                    v[i+1][j] = 1;
                    v[i][j+1] = 1;
                    v[i+1][j+1] = 1;
                }
            }
        }
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(v[i][j] == 1){
                    board[i][j] = 'x';
                    cnt++;
                    flag = 1;
                }
            }
        }
        
        if(flag == 0)
            break;
        
        for(int i=0;i<n;i++){
            for(int j=m-1;j>=0;j--){
                if(board[j][i] != 'x')
                    continue;
                for(int k=j;k>=0;k--){
                    if(board[k][i] != 'x'){
                        board[j][i] = board[k][i];
                        board[k][i] = 'x';
                        break;
                    }
                }
            }
        }
    }    
    answer = cnt;
    return answer;
}

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