[Algorithm] Programmers :: 프렌즈4블록

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

프로그래머스

bool destroyCheck[31][31] = { false };
vector<string> board;
 
int Destroy()
{
    int count = 0;
    memset(destroyCheck, false, sizeof(destroyCheck));
 
    for (int i = 0; i < board.size() - 1; ++i)
    {
        for (int j = 0; j < board[0].size() - 1; ++j)
        {
            char standard = board[i][j];
 
            if (standard == '?') continue;
 
            if (board[i + 1][j] == standard && board[i][j + 1] == standard && board[i + 1][j + 1] == standard)
            {
                destroyCheck[i][j] = true;
                destroyCheck[i + 1][j] = true;
                destroyCheck[i][j + 1] = true;
                destroyCheck[i + 1][j + 1] = true;
            }
        }
    }
 
    for (int i = 0; i < board.size(); ++i)
    {
        for (int j = 0; j < board[0].size(); ++j)
        {
            if (destroyCheck[i][j])
            {
                ++count;
                board[i][j] = '?';
            }
        }
    }
 
    return count;
}
 
void Down()
{
    for (int i = 0; i < board[0].size(); ++i)
    {
        int count = 0;
        bool isChecking = false;
 
        for (int j = board.size() - 1; j >= 0; --j) // 아래에서 위로
        {
            if (board[j][i] == '?')
            {
                isChecking = true;
                ++count;
            }
            else
            {
                if (isChecking)
                {
                    board[j + count][i] = board[j][i];
                    board[j][i] = '?';
                }
            }
        }
    }
}
 
 
int solution(int m, int n, vector<string> _board)
{
    int answer = 0;
    board = _board;
 
    while (1)
    {
        int destroyedNodes = Destroy();
        if (destroyedNodes == 0) break;
        answer += destroyedNodes;
 
        Down();
    }
 
    return answer;
}

 

크게 어렵지 않은 구현문제인데, 한번 풀어보는걸 추천한다.

백준에서 추천문제집에 있는 문제들 풀다보면 비슷한 유형의 문제들이 더러 있었다.

블록 삭제 후, 밑으로 떨어뜨리는부분을 연습해보면 좋을 듯 하다.