[알고리즘C++][1차] 프렌즈4블록

오늘의 문제

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

프렌즈4블록

나의 풀이

#include <string>
#include <vector>

using namespace std;
vector<vector<int>> square;
vector<string> board;
int answer = 0;

void detectSquare(int m, int n){
    for(int i=0;i<m-1;i++){
        for(int j=0;j<n-1;j++){
            char c = board[i][j];
            if(c == '0')
                continue;
            if(c == board[i][j+1] && c == board[i+1][j+1] && c == board[i+1][j]){
                square.push_back({i, j});
            }
        }
    }
    if(square.size() != 0){
    // 삭제
    for(int i=0;i<square.size();i++){
        int row = square[i][0];
        int col = square[i][1];
        if(board[row][col] != '0'){
            board[row][col] = '0';
            answer++;
        }
        if(board[row+1][col] != '0'){
            board[row+1][col] = '0';
            answer++;
        }
         if(board[row][col+1] != '0'){
            board[row][col+1] = '0';
            answer++;
        }
         if(board[row+1][col+1] != '0'){
            board[row+1][col+1] = '0';
            answer++;
        }
    }
    
    // 내리기
    int down = 0;
    bool fill = false;
    for(int j=0;j<n;j++){
        fill = false;
        for(int i= m-1 ;i>=0;i--){
            if(board[i][j] == '0'){
                if(!fill){
                    fill = true;
                    down = i;
                }
            }else{
                if(fill){
                    board[down][j] = board[i][j];
                    board[i][j] = '0';
                    down--;
                }
            }
        }
    }
    square.clear();
    detectSquare(m, n);
    }
}
int solution(int m, int n, vector<string> b) {
    board = b;
    detectSquare(m, n);
    return answer;
}

모범 답안

#include <string>
#include <vector>
#include <queue>

using namespace std;

int M, N;
vector<vector<bool>> v;
int solution(int m, int n, vector<string> board);
bool check(int ii, int jj, vector<string> board);
vector<string> erase(vector<string> board);

int solution(int m, int n, vector<string> board) {
    M = m;
    N = n;
    int answer = 0;
    bool flag = false;
    while (!flag) {
        v = vector<vector<bool>>(m, vector<bool>(n, false));
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == 'x') 
                    continue;
                if (check(i, j, board))
                    flag = true;
            }
        }
        if (!flag) break;
        board = erase(board);
        flag = false;
    }

    //answer계산
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'x')
                answer++;
        }
    }

    return answer;
}

//지울 블럭이 있으면 true, 없으면 false 반환
bool check(int ii, int jj, vector<string> board) {
    int iter_x[3] = { 1,1,0 };
    int iter_y[3] = { 0,1,1 };
    char c = board[ii].at(jj);

    for (int i = 0; i < 3; i++) {
        int next_x = jj + iter_x[i];
        int next_y = ii + iter_y[i];
        if (next_x >= N || next_y >= M || 
            c != board[next_y].at(next_x)) {
            return false;
        }
    }

    v[ii][jj] = true;
    for (int i = 0; i < 3; i++) {
        int next_x = jj + iter_x[i];
        int next_y = ii + iter_y[i];
        v[next_y][next_x] = true;
    }
    return true;
}

vector<string> erase(vector<string> board) {
    for (int i = 0; i < N; i++) {
        queue<char> q;
        for (int j = M -1; j >= 0; j--) {
            if (v[j][i]) //지워야할블럭
                continue;
            q.push(board[j][i]);
        }
        for (int j = M - 1; j >= 0; j--) {
            if (q.empty())
                board[j][i] = 'x';
            else {
                board[j][i] = q.front();
                q.pop();
            }
        }
    }
    return board;
}

배울 점

• 나도 저 사람처럼 나눠서 하려다가 걍 재귀로 구현했다. 방식은 비슷한듯 하다.
• 코드를 작성하기 전에 종이에 내가 생각해낸 아이디어를 먼저 작성하고 시작하니 헷갈리지 않았다. 저번에 카카오 코테에서 왼손 미로찾기 문제를 풀 때 x, y랑 row column을 섞어쓰다 개 헷갈려서 오래걸렸는데 이런 점을 방지 할 수 있을 것 같다.
• 우선 x, y 좌표인지 row, colum 을 분명하게 구분하고 시작해야한다.