프렌즈4블록 C++ 2018 KAKAO Blind Recruitment

문제 설명

프렌즈4블록

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈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

예제에 대한 설명

• 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
• 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

구현

문제를 보자마자 든 생각은 vector의 erase를 잘만 활용하면 아주 쉽게 풀 수 있겠다는 생각이었다.

더 이상 블록을 제거할 수 없을 때 까지 반복문을 돌리기만하면 되는 문제라서 실제로 2018 카카오 해설집에서는 문제의 난이도가 上으로 표현돼있지만 프로그래머스에서도 Level2라고 표현했듯 상당히 쉬운 축에 속하는 문제인 것 같다.

우선 입력으로 들어온 board vector를 아래에서부터 처리해야하기 때문에 90도를 회전하여 새로운 vector에 저장해 주었다.

vector<string> temp;
for (int i = 0; i < n; i++)
{
  string tmp = "";
  for (int j = m - 1; j >= 0; j--)
  {
  	tmp = tmp + board[j][i];
  }
  temp.push_back(tmp);
}

---

이후 do while문을 사용하며 제거되지 않은 경우가 있을 경우 flga를 0으로 하여 반복문을 탈출 하는 구조를 만들기로 생각했고 이렇게 작업을 수행할 시에 분명하게도 중복되는 좌표가 겹칠 수가 있다.

또한 4개 정사각형이 만들어지는 즉시 제거하는 것이 아니라 board에 있는 모든 가능한 2 x 2 형태의 표현을 한 번에 제거해야하기 때문에 각 좌표를 저장하는 방식으로 구현하였다.

do
{
  flag = 0;
  set<pair<int, int>> s;
  for (int i = 0; i < temp.size() - 1; i++)
  {
    if (temp[i].size() <= 0)
    	continue;
    for (int j = 0; j < temp[i].size() - 1; j++)
    {
    if (check(i, j, temp))
    {
      s.insert(make_pair(i, j));
      s.insert(make_pair(i, j + 1));
      s.insert(make_pair(i + 1, j));
      s.insert(make_pair(i + 1, j + 1));
      flag = 1;
    }
    }
  }
  for (auto iter = s.rbegin(); iter != s.rend(); iter++)
  {
    temp[iter->first].erase(temp[iter->first].begin() + iter->second);
    answer++;
  }
} while (flag);

set 자료구조를 통하여 중복되는 좌표는 자연스럽게 제거해주었고 다만 구현하다보니 한 줄의 모든 블록이 사라졌을 때 문제가 발생하는 것을 보고 블록이 모두 사라졌을 경우 반복문을 계속 진행하도록 구현하였다.

또한 set 자료구조에 들어간 좌표들을 앞에서부터 erase해 줄 경우 삭제된 블록 뒤에 있는 블록들의 좌표가 바뀌기 때문에 set의 뒤부터 (좌표가 큰 순서부터) 제일 앞까지 제거해주는 방식으로 구현하였다.

---

전체 코드는 아래에서 볼 수 있다.

#include <string>
#include <vector>
#include <set>

using namespace std;

int check(int x, int y, vector<string> board)
{
    if (!board[x][y])
        return 0;
    if (board[x][y] != board[x][y + 1])
        return 0;
    if (board[x][y] != board[x + 1][y])
        return 0;
    if (board[x][y] != board[x + 1][y + 1])
        return 0;
    return 1;
}

int solution(int m, int n, vector<string> board)
{
    int answer = 0;
    int flag;
    vector<string> temp;
    for (int i = 0; i < n; i++)
    {
        string tmp = "";
        for (int j = m - 1; j >= 0; j--)
        {
            tmp = tmp + board[j][i];
        }
        temp.push_back(tmp);
    }

    do
    {
        flag = 0;
        set<pair<int, int>> s;
        for (int i = 0; i < temp.size() - 1; i++)
        {
            if (temp[i].size() <= 0)
                continue;
            for (int j = 0; j < temp[i].size() - 1; j++)
            {
                if (check(i, j, temp))
                {
                    s.insert(make_pair(i, j));
                    s.insert(make_pair(i, j + 1));
                    s.insert(make_pair(i + 1, j));
                    s.insert(make_pair(i + 1, j + 1));
                    flag = 1;
                }
            }
        }
        for (auto iter = s.rbegin(); iter != s.rend(); iter++)
        {
            temp[iter->first].erase(temp[iter->first].begin() + iter->second);
            answer++;
        }
    } while (flag);
    return answer;
}