[C++] 프로그래머스 [1차] 프렌즈4블록

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

프로그래머스

풀이

1. board 에서 2x2 구획을 만들어 삭제될 수 있는 좌표를 검색합니다. 이 때, 가능한 모든 칸을 한번에 삭제해야 하므로 탐색이 완전히 끝난 후 삭제 처리해야 합니다. 

2. 삭제할 수 있다면 set<vector<int>> 자료형 check 변수에 좌표를 insert 한다. 이 때, 중복을 혀용하지 않으므로 별도의 예외처리가 필요하지 않습니다.

3. 검색을 진행한 후 check 변수가 비어있지 않다면 삭제할 수 있는 칸이 있으므로 drop_block을 사용해 삭제('#'처리 및 위로 올리기)를 진행합니다. 

4. 삭제된 구획을 위로 올리는 방법은 swap함수를 사용합니다.

5. 재귀적으로 check_board를 호출하여 최종 답을 도출합니다.

 

리뷰 

삭제된 구획을 처리하는 방법에 유의합니다. 역방향으로 순회하며 swap처리 시 현재 값을 가장 앞으로 보낼 수 있습니다. 

#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>

using namespace std;

void drop_block(vector<string>& board, set<vector<int>> check);

int check_board(int m, int n, vector<string> board) {
    set<vector<int>> check;
    
    // 2x2 매트릭스로 찾음
    for (int i = 0; i < m - 1; i++) {
        for (int j = 0; j < n - 1; j++) {
            if (board[i][j] != '#' && board[i][j] == board[i + 1][j]) {
                if (board[i][j + 1] == board[i + 1][j + 1]) {
                    if (board[i][j] == board[i + 1][j + 1]) {
                        check.insert({i, j});
                        check.insert({i, j + 1});
                        check.insert({i + 1, j});
                        check.insert({i + 1, j + 1});
                    }
                }
            }
            
        }
    }
    
    if (check.empty()) {
        return 0;
    }
    else {
        drop_block(board, check);
        // 재귀
        return check.size() + check_board(m, n, board);
    }
}

void drop_block(vector<string>& board, set<vector<int>> check) {
    for (const auto& idx : check) {
        board[idx[0]][idx[1]] = '#';
        for (int i = idx[0]; i > 0; i--) {
            swap(board[i][idx[1]], board[i - 1][idx[1]]);
        }
    }
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;

    answer = check_board(m, n, board);
    
    return answer;
}