문제 푼 날짜 : 2021-07-26

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17679

접근 및 풀이

주어진 배열의 크기가 최대 30x30로 그다지 크지 않아서 완전탐색으로 풀면 되겠다는 생각을 하였다.
구현은 아래와 같은 알고리즘으로 구현하였다.

1. (0, 0) 지점부터 (m - 2, n - 2)까지 탐색한다.
2. 탐색하면서 각 위치에서 오른쪽, 아래쪽, 오른아래쪽(대각선방향)에 같은 모양의 블록이 있다면 표시를 해준다.
3. 표시된 블록들을 '0'으로 치환해준다.
4. 각 열별로 블록들을 아래로 떨어트린다.
5. 표시된 블록이 없을 때까지 1.부터 반복한다.

(m - 2, n - 2) 까지 탐색한 이유는 정사각형을 체크할때 범위를 벗어나지 않게하기 위해서 였다. 구현하기 어렵지 않은 문제였던 것 같다.
더 쉽게 구현할 수도 있을 것 같지만,,, 그냥 문제에 주어진대로 순서대로 구현하였다.

코드

#include <string>
#include <vector>
#include <cstring>

using namespace std;

int M, N;
vector<string> cBoard;

bool visited[31][31];
int dir[3][2] = {{ 1, 0 }, { 1, 1 }, { 0, 1 }};

bool square_check(int y, int x, char ch) {
    bool flag = true;
    for (int n = 0; n < 3; n++) {
        if (cBoard[y + dir[n][0]][x + dir[n][1]] != ch) {
            flag = false;
            break;
        }
    }
    if (flag) {
        visited[y][x] = true;
        for (int n = 0; n < 3; n++) {
            visited[y + dir[n][0]][x + dir[n][1]] = true;
        }
    }
    return flag;
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    M = m, N = n, cBoard = board;
    bool erase = false;

    do {
        erase = false;
        memset(visited, false, sizeof(visited));
        for (int i = 0; i < m - 1; i++) { // 지울 블록 체크
            for (int j = 0; j < n - 1; j++) {
                if (cBoard[i][j] != '0') {
                    if (square_check(i, j, cBoard[i][j])) {
                        erase = true;
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) { // 블록 지우기('0'으로 치환)
            for (int j = 0; j < n; j++) {
                if (visited[i][j] == true) {
                    cBoard[i][j] = '0';
                    answer++;
                }
            }
        }
        int y, x;
        for (int i = 0; i < n; i++) { // 각 열별로 블록들 떨어트리기
            for (int j = m - 1; j >= 0; j--) {
                if (cBoard[j][i] == '0') {
                    y = j, x = i;
                    bool change = false;
                    while (true) {
                        y--;
                        if (y < 0) {
                            break;
                        }
                        if (cBoard[y][x] != '0') {
                            change = true;
                            break;
                        }
                    }
                    if (change == true) {
                        cBoard[j][i] = cBoard[y][x];
                        cBoard[y][x] = '0';
                    }
                }
            }
        }
    } while (erase); // 지워지는게 없으면 종료
    return answer;
}

결과

피드백

구현능력이 중요한 문제였던 것 같다.