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

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

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

bool cal(int& answer, vector<string>& board)
{
    vector<pair<int, int>> savePos;
    vector<string> chB;
    for (int i = 0; i < board.size(); i++)
    {
        string s = "";
        for (int j = 0; j < board[i].length(); j++)
        {
            s += (board[i][j] == ' ') ? '0' : '1';
        }
        chB.push_back(s);
    }
    for (int i = 0; i < board.size() - 1; i++)
    {
        for (int j = 0; j < board[i].size() - 1; j++)
        {
            if (board[i][j] == ' ')continue;
            if ((board[i][j] == board[i][j + 1]) && (board[i][j + 1] == board[i + 1][j]) &&
                (board[i + 1][j] == board[i + 1][j + 1]))
            {
                // 4개 일치
                for (int r = i; r <= i + 1; r++)
                    for (int c = j; c <= j + 1; c++)
                        if (chB[r][c] == '1') { answer++; chB[r][c] = '0'; }

                savePos.push_back({ i,j });
            }
        }
    }
    if (savePos.size() == 0)return false;

    for (auto item : savePos)
    {
        board[item.first][item.second] = ' ';
        board[item.first][item.second + 1] = ' ';
        board[item.first + 1][item.second] = ' ';
        board[item.first + 1][item.second + 1] = ' ';
    }

    return true;
}

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

    while (cal(answer, board))
    {
        for (int i = 0; i < board[0].size(); i++)
        {
            for (int j = board.size()-1; j >=1 ; j--)
            {
                if (board[j][i] == ' ')
                {
                    int k = j-1;
                    while (k >= 1 && board[k][i] == ' ')
                        k--;
                    if (k == 0 && board[k][i] == ' ')
                        continue;
                    board[j][i] = board[k][i];
                    board[k][i] = ' ';
                }
            }

        }
    }

    return answer;
}

 

게임 기능을 만드는 문제인데 블록모양의 배열이 주어지고 각 원소는 대문자로 표시되어있다. 

사각형의 4블록이 동일하면 사라지고 빈칸은 위에있던 블록이 메운다. 

이 때, 한 블록은 여러 4블록에 사용이 가능하다. 

 

알고리즘은 다음과 같다. 

1. 한 블록이 중복되어 사용될 수 있기 때문에 사용됐던 것인지 체크하는 배열을 하나 만든다. 

2. 4개가 동일한 경우를 찾는다. 

3. 사용안됐던 블록은 카운트하고 사용처리한다. 

4. 종료 후, 4개의 블록을 board에서 빈공간처리한다. 

5. 빈공간을 다시 채운다. -> 1번으로 돌아간다.  

 

1~3번은 cal이라는 함수로 만들어서 처리했다. 

또 4~5번을 반복하기 위해선 solution 함수에서 while을 통해 처리한다. 

 

bool cal(int& answer, vector<string>& board)
{
    vector<pair<int, int>> savePos;
    vector<string> chB;
    for (int i = 0; i < board.size(); i++)
    {
        string s = "";
        for (int j = 0; j < board[i].length(); j++)
        {
            s += (board[i][j] == ' ') ? '0' : '1';
        }
        chB.push_back(s);
    }
    for (int i = 0; i < board.size() - 1; i++)
    {
        for (int j = 0; j < board[i].size() - 1; j++)
        {
            if (board[i][j] == ' ')continue;
            if ((board[i][j] == board[i][j + 1]) && (board[i][j + 1] == board[i + 1][j]) &&
                (board[i + 1][j] == board[i + 1][j + 1]))
            {
                // 4개 일치
                for (int r = i; r <= i + 1; r++)
                    for (int c = j; c <= j + 1; c++)
                        if (chB[r][c] == '1') { answer++; chB[r][c] = '0'; }

                savePos.push_back({ i,j });
            }
        }
    }
    if (savePos.size() == 0)return false;

    for (auto item : savePos)
    {
        board[item.first][item.second] = ' ';
        board[item.first][item.second + 1] = ' ';
        board[item.first + 1][item.second] = ' ';
        board[item.first + 1][item.second + 1] = ' ';
    }

    return true;
}

cal 함수인데 bool 값을 리턴한다. 

4개가 동일한 블록이 하나라도 있었으면 true 아니면 false이다. 

 

먼저 chB배열이 사용됐었는지 체크하는 배열이다.(사용됐거나 빈칸이면 0 아니면 1이다.)

또 savePos는 기준점인 i,j 지점을 저장하는 역할이다. 

for문에서 i,j 를 기준으로 오른쪽, 아래, 대각선을 확인하기 때문.

 

if ((board[i][j] == board[i][j + 1]) && (board[i][j + 1] == board[i + 1][j]) &&
                (board[i + 1][j] == board[i + 1][j + 1]))
            {
                // 4개 일치
                for (int r = i; r <= i + 1; r++)
                    for (int c = j; c <= j + 1; c++)
                        if (chB[r][c] == '1') { answer++; chB[r][c] = '0'; }

                savePos.push_back({ i,j });

이중 for문을 돌며 4개가 일치하는 경우 각 칸에 대해서 사용됐던 것인지 판단하고 처리한다. 

그리고 그 좌표를 savePos에 저장한다. 

 

if (savePos.size() == 0)return false;

    for (auto item : savePos)
    {
        board[item.first][item.second] = ' ';
        board[item.first][item.second + 1] = ' ';
        board[item.first + 1][item.second] = ' ';
        board[item.first + 1][item.second + 1] = ' ';
    }

    return true;

모든 좌표를 살펴보고 저장된 좌표가 없다면 false리턴

아니면 savePos를 순회하면서 board를 빈공간으로 표시한다. 

 

while (cal(answer, board))
    {
        for (int i = 0; i < board[0].size(); i++)
        {
            for (int j = board.size()-1; j >=1 ; j--)
            {
                if (board[j][i] == ' ')
                {
                    int k = j-1;
                    while (k >= 1 && board[k][i] == ' ')
                        k--;
                    if (k == 0 && board[k][i] == ' ')
                        continue;
                    board[j][i] = board[k][i];
                    board[k][i] = ' ';
                }
            }

        }
    }

solution에서 while문을 통해 cal함수를 계속 호출한다. 

리턴결과가 true면 바뀐결과가 있으므로 이중 for문을 통해 빈공간을 채우는 작업을 한다.

한 열씩 보면서 아래쪽부터 내려할 블록이 있으면 while문을 통해 쌓일 좌표까지 내린다.