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

프로그래머스의 [1차]프렌즈4블록(Lv2) 문제이다.

[ 문제풀이 ]

알고리즘이나 문제에 접근하는 것에 대해서는 별다른 설명이 필요하지 않은 문제라고 생각한다.

따라서, 코드와 코드에 대한 설명으로 대체하겠다.

# 2 x 2 블록인지 확인하는 과정

int dx[] = { 0, 1, 1 };
int dy[] = { 1, 0, 1 };
 
bool Check(int x, int y, vector<string> board)
{
    for (int i = 0; i < 3; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= N || ny >= M) return false;
        if (board[x][y] != board[nx][ny]) return false;
    }
    return true;
}

본인이 구현한 (x , y)를 기준으로 2 x 2칸이 지워질 수 있는지 Check 하는 함수이다.

매개변수로 (x , y)를 호출하고, (x , y)를 기준으로, 오른쪽, 아래쪽, 오른쪽아래 대각선, 이렇게 3칸을 확인하면서

판단해 주었다.

중요한 것은, 위의 코드에서는 나와있지 않지만, 지울 수 있는 칸이라고 해서 바로 지워버리면 안된다.

왜냐하면 다음과 같은 경우가 발생할 수 있기 때문이다.

.

가장 왼쪽 위에 있는 (0 , 0) 'A'에서 위의 Check함수를 실행시킨다면, (0 , 0), (0 , 1), (1 , 0) , (1 , 1)이 모두 'A'이기 떄문에 지울 수 있는 좌표라는 결과가 반환될 것이다.

하지만 바로 지워버린다면 ??

.

위와 같이 표시된 파랑색 칸을 계산할 때 굉장히 애매해진다.

지워질 수 있는 칸임에도 불구하고, 파랑색으로 표시된 4칸이 모두 같은 모양이 아니기 때문에 지울 수 없다고 판단할 수도 있다. 따라서, 본인은 바로 지우지 않고 지울 수 있는 좌표들만 Vector에 따로 저장해 주었다.

# 블럭을 지우는 과정

int Delete_Block(vector<pair<int, int>> V, vector<string> &board)
{
    int Cnt = 0;
    for (int i = 0; i < V.size(); i++)
    {
        int x = V[i].first;
        int y = V[i].second;
        if (board[x][y] != '.')
        {
            board[x][y] = '.';
            Cnt++;
        }
 
        for (int j = 0; j < 3; j++)
        {
            int nx = x + dx[j];
            int ny = y + dy[j];
            if (board[nx][ny] != '.')
            {
                Cnt++;
                board[nx][ny] = '.';
            }
        }
    }
    return Cnt;
}

본인이 구현한 실제로 블럭을 지우는 과정이다. 동시에, "지운 블럭의 갯수를 return" 하도록 구현한 함수이다.

매개변수로 호출되는 V가 "지울 수 있는 좌표를 저장" 해놓은 Vector를 의미한다.
.

위의 맵을 예시로 들어보면, Vector에는 (0 , 0)과 (1 , 1)이 저장되어 있을 것이다.

왜냐하면, (0 , 0)에서 2 x 2 칸, (1 , 1)에서 2 x 2 칸을 지울 수 있기 때문이다.

그런데, 실질적으로 지워지는 칸은 8칸이 아닌 7칸이다. 왜냐하면 (1 , 1)이 중복이 되기 때문이다.

따라서, 위의 코드에서 line8과 line18과 같이, 아직 지워지지 않은 칸에 대해서만 지운 블록의 갯수를 ++ 해주었다.

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
int N, M;
int dx[] = { 0, 1, 1 };
int dy[] = { 1, 0, 1 };
 
bool Check(int x, int y, vector<string> board)
{
    for (int i = 0; i < 3; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= N || ny >= M) return false;
        if (board[x][y] != board[nx][ny]) return false;
    }
    return true;
}
 
int Delete_Block(vector<pair<int, int>> V, vector<string> &board)
{
    int Cnt = 0;
    for (int i = 0; i < V.size(); i++)
    {
        int x = V[i].first;
        int y = V[i].second;
        if (board[x][y] != '.')
        {
            board[x][y] = '.';
            Cnt++;
        }
 
        for (int j = 0; j < 3; j++)
        {
            int nx = x + dx[j];
            int ny = y + dy[j];
            if (board[nx][ny] != '.')
            {
                Cnt++;
                board[nx][ny] = '.';
            }
        }
    }
    return Cnt;
}
 
void Arrange_MAP(vector<string> &board)
{
    for (int i = N - 1; i >= 0; i--)
    {
        for (int j = 0; j < M; j++)
        {
            if (board[i][j] == '.') continue;
            
            int nx = i + 1;
            while (nx < N && board[nx][j] == '.') nx++;
            nx--;
            if (nx != i)
            {
                board[nx][j] = board[i][j];
                board[i][j] = '.';
            }
        }
    }
}
 
int solution(int m, int n, vector<string> board) 
{
    N = m;
    M = n;
    int answer = 0;
    bool Flag = true;
 
    while (Flag == true)
    {
        Flag = false;
        vector<pair<int, int>> V;
        vector<vector<bool>> Visit(N, vector<bool>(M, false));
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (board[i][j] == '.') continue;
                if (Check(i, j, board) == true)
                {
                    V.push_back(make_pair(i, j));
                    Flag = true;
                }
            }
        }
 
        if (Flag == true)
        {
            answer = answer + Delete_Block(V, board);
            Arrange_MAP(board);
        }
    }
    return answer;
}