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

문제 설명

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 프렌즈4블록.
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

위 초기 배치를 문자로 표시하면 아래와 같다.

TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

 

입력 형식

• 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
• 2 ≦ n, m ≦ 30
• board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

 

출력 형식

입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

 

입출력 예

m	n	board	answer
4	5	[CCBDE, AAADE, AAABF, CCBBF]	14
6	6	[TTTANT, RRFACC, RRRFCC, TRRRAA, TTMMMF, TMMTTJ]	15

 

 

코드

#include <string>
#include <vector>

using namespace std;

bool find_block(vector<vector<pair<char, int>>> &v)
{
    int i;
    int j;
    char block;
    bool more = false;
    
    for (i = 1; i < v.size(); i++)
    {
        for (j = 1; j < v[i].size(); j++)
        {
            block = v[i][j].first;
            if (v[i][j - 1].first != block)
                continue;
            if (v[i - 1].size() <= j - 1)
                continue;
            if (v[i - 1][j].first != block)
                continue;
            if (v[i - 1][j - 1].first != block)
                continue;
            more = true;
            v[i][j].second = true;
            v[i][j - 1].second = true;
            v[i - 1][j].second = true;
            v[i - 1][j - 1].second = true;
        }
    }
    return more;
}

int erase_block(vector<vector<pair<char, int>>> &v, int answer)
{
    int i;
    int j;
    
    for (i = 0; i < v.size(); i++)
    {
        for (j = 0; j < v[i].size(); j++)
        {
            if (v[i][j].second)
            {
                answer++;
                v[i].erase(v[i].begin() + j);
                j--;
            }
        }
    }
    return answer;
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    int i, j;
    bool more = true;
    char block;
    vector<vector<pair<char, int>>> v;
    vector<pair<char, int>> tmp;
    
    for (i = 0; i < n; i++)
    {
        for (j = m - 1; j >= 0; j--)
        {
            tmp.push_back(make_pair(board[j][i], 0));
        }
        v.push_back(tmp);
        tmp.clear();
    }
    while (more)
    {
        more = false;
        if (find_block(v))
            more = true;
        answer = erase_block(v, answer);
    }
    return answer;
}

 

2 X 2 블럭이 존재하지 않을 때까지 모든 2 X 2 블럭을 찾고, 찾은 블럭을 삭제하는 과정을 반복한다.

매개변수로 주어진 string형 벡터는 블럭을 삭제하고 올바른 위치까지 조정해 주어야 해서 복잡하다. 따라서 string형 벡터를 시계 방향으로 90도 회전된 char형 2차원 벡터로 옮겨주었다. pair를 사용한 이유는 두 번째 원소로 해당 블럭이 2 X 2 블럭에 포함되는지 나타내기 위해서다.

이렇게 나타내면 erase 함수를 사용하는 것만으로도 퍼즐의 동작을 나타낼 수 있다. 

먼저, find_block() 함수에서 2 X 2 블럭을 찾아 해당 블럭의 두 번째 원소를 1로 설정한다. 현재 board를 기준으로 모든 2 X 2 블럭을 찾으면 erase_block() 함수에서 두 번째 원소가 1인 블럭을 찾아 삭제하고, answer를 1만큼 증가시킨다. 여기서 j--를 해준 이유는 j번째 인덱스의 값이 삭제되어 뒤에 있던 값이 앞으로 밀려왔으므로 j++이 바로 수행되면 모든 값을 확인하지 못하기 때문이다.

현재 board를 기준으로 2 X 2 블럭이 하나도 없었다면 반복을 종료하고 return한다.

 

링크

programmers.co.kr/learn/courses/30/lessons/17679

코딩테스트 연습 - [1차] 프렌즈4블록

github.com/inbdni/Programmers/blob/master/level02/%ED%94%84%EB%A0%8C%EC%A6%884%EB%B8%94%EB%A1%9D.cpp

inbdni/Programmers