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

문제

 

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

프로그래머스

 

 

문제풀이

 

꼭 2*2 블록만이 지워지는 것이 아닌 2*4, 3*3 이런 식으로 여러 형태로 지워질 수 도 있다.

따라서 모든 y, x를 탐색하면서 해당 블록과 인접한 3개의 블록이 같은지를 판별해야 한다.

 

해당 블록과 인접한 3개의 블록이 같은지, 범위를 벗어나는지, 이미 지운 블록인지를 판별하는 함수를 구현한다.

지워야 하는 블록을 지우는 함수를 구현한다.

 

    loc.insert({ -1,-1 });
    while (!loc.empty()) {
        loc.clear();
        for (int y = board.size() - 1; y >= 0; --y) {
            for (int x = 0; x < board[y].size(); ++x) {
                findBlocks(y, x);
            }
        }
        answer += loc.size();
        eraseBlocks();
    }

먼저 메인문이다.

왼쪽 위 좌표를 (0, 0)으로 두고 오른쪽, 아래로 갈수록 값이 커지도록 했다.

모든 좌표의 블록들을 탐색한다.

 

findBlocks 함수를 통해 set <pair <int, int>> loc에 지워야 하는 블록의 좌표를 저장한다.

만약 지워야 할 블록이 없다면 반복문이 종료된다.

처음에 반복문을 실행하기 위해 loc에 아무 값을 저장했다. 바로 clear 되기 때문에 정답에 영향이 없다.

 

그다음 eraseBlocks함수를 통해 지워야 하는 블록들을 지운다.

 

void findBlocks(int y, int x) {
    if (y - 1 < 0 || x >= board[y].size()) return;

    char c1 = board[y][x];
    char c2 = board[y][x + 1];
    char c3 = board[y - 1][x];
    char c4 = board[y - 1][x + 1];

    if (c1 == '0') return;
    if (c1 == c2 && c1 == c3 && c1 == c4) {
        loc.insert({ y, x });
        loc.insert({ y, x + 1 });
        loc.insert({ y - 1, x });
        loc.insert({ y - 1, x + 1 });
    }
}

보기 편하기 위해 각 블록들을 char형 변수에 저장했다.

현재 좌표로부터 현재 블록, 오른쪽 블록, 위쪽 블록, 오른쪽 위 블록을 구할 것이다.

범위에 벗어난다면 return 한다.

 

만약 현재 블록이 지워야 하는 블록이라면 return 한다.

(주어지는 블록들은 알파벳 대문자 이므로 지워야 하는 블록은 그 외의 문자를 이용해야 한다.)

 

만약 모두 같은 블록이라면 loc에 네 좌표를 저장한다.

 

void eraseBlocks() {
    for (auto iter = loc.begin(); iter != loc.end(); ++iter) {
        board[iter->first][iter->second] = '0';
    }

    for (int y = board.size() - 1; y >= 0; --y) {
        for (int x = 0; x < board[y].size(); ++x) {
            if (board[y][x] == '0') {
                int ny = y - 1;
                while (ny >= 0 && board[ny][x] == '0') --ny;
                if (ny < 0) continue;
                else {
                    swap(board[y][x], board[ny][x]);
                }
            }
        }
    }
}

지우는 함수이다.

좌표를 통해 바로 지우면 계속 바뀌는 블록에 의해 답을 구하기 어려워지므로 미리 0으로 모두 바꾼다.

 

블록들은 위에서 아래로 떨어지므로 y는 맨 아래부터 탐색한다.

만약 현재 블록이 지워야 하는 블록이면 한 칸 위부터 지워야 하는 블록이 아닌 생존해 있는 블록일 때까지 y를 계속 한 칸씩 움직인다.

만약 범위를 벗어났다면 넘어간다.

그렇지 않다면 생존해 있는 블록과 swap 한다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#define pii pair<int, int>
using namespace std;
vector<string>board;
set<pii>loc;

void findBlocks(int y, int x) {
    if (y - 1 < 0 || x >= board[y].size()) return;

    char c1 = board[y][x];
    char c2 = board[y][x + 1];
    char c3 = board[y - 1][x];
    char c4 = board[y - 1][x + 1];

    if (c1 == '0') return;
    if (c1 == c2 && c1 == c3 && c1 == c4) {
        loc.insert({ y, x });
        loc.insert({ y, x + 1 });
        loc.insert({ y - 1, x });
        loc.insert({ y - 1, x + 1 });
    }
}

void eraseBlocks() {
    for (auto iter = loc.begin(); iter != loc.end(); ++iter) {
        board[iter->first][iter->second] = '0';
    }

    for (int y = board.size() - 1; y >= 0; --y) {
        for (int x = 0; x < board[y].size(); ++x) {
            if (board[y][x] == '0') {
                int ny = y - 1;
                while (ny >= 0 && board[ny][x] == '0') --ny;
                if (ny < 0) continue;
                else {
                    swap(board[y][x], board[ny][x]);
                }
            }
        }
    }
}

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

    loc.insert({ -1,-1 });
    while (!loc.empty()) {
        loc.clear();
        for (int y = board.size() - 1; y >= 0; --y) {
            for (int x = 0; x < board[y].size(); ++x) {
                findBlocks(y, x);
            }
        }
        answer += loc.size();
        eraseBlocks();
    }
    return answer;
}