[C++/Programmers] Lv2. 프렌즈 4 블록

코테 연습을 하다가 기록 해 두면 좋을 것 같아서 블로그에도 백업? 해 두려고 한다.

---

문제

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 

이번에 출시할 게임 제목은 "프렌즈4블록".

같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

점수 획득 조건

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 

같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

빈 공간을 떨어지면서 채우게 된다

떨어지고 난 뒤, 다시 4블록이 맞춰지는 경우

만약 빈 공간을 채운 후에 다시 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가 사용된다.

---

출력 형식

 

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

---

생각 해 보기

조금 복잡하게 보일 수 있긴 하지만..

 

나는 일단 새롭게 자료구조를 하나 더 만들어 문제를 접근 해 보기로 하였다.

 

즉, 4개가 뭉쳤는지 여부를 나타내어 삭제하면서 카운트를 세는 용도의 이차원 벡터를 하나 만들어 주었다.

 

이차원 벡터의 초기값 세팅은 이 사이트를 참고 하였다.

C++에서 2차원 벡터 초기화

순차적으로 M(높이), N(길이)를 세팅할 수 있다.

 

하나씩 자료를 순회하면서 자신과 우측 1칸 옆, 1칸 아래, 오른쪽 아래(대각선) 원소와 같은지를 따진다. (왼쪽 → 오른쪽, 위 → 아래 쪽으로 가기 때문에 가능하다)

 

모두가 같다면(&&로 판별) 4개가 모여 있는 것이기 때문에 따로 만든 자료 구조에 1로 표시를 해 준다.

 

그리고 한 바퀴를 돌았다면 따로 만든 자료구조를 순회하면서 0으로 바꾸고, 원래 board에 ‘.’으로 표시 해 가면서 answer를 더해 준다.

 

만약에 4개 블록이 있는지 판별하면서 한 개도 발견되지 않았을 경우에는 바로 while문을 빠져나와 준다.

 

그리고 개인적으로 좀 실수했던 부분이다.

 

블록을 아래로 떨어트리는 부분인데.. 여기서 index를 줄이고 늘리는 것을 착각했다.

 

바로 아래에서 한 줄씩 위로 올라가면서 탐색을 하며, ‘.’이 있는 경우에는 위로 한번 더 올려 주고, ‘.’이 아니면 아래(인덱스는 증가!!!)에 있는 놈이 ‘.’인지 확인하는 작업을 반복하여 실행(for문 사용) 해 준다.

블록 떨구기

 

반복은 맨 아래에서 한 칸 위 까지(높이 - 2 index)실행 해 준다. (인덱스 증가이다!!)

 

아무튼 이 것을 코드로 작성하여 낸 것이 아래에 있다.

---

코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

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

    vector<vector<int>> checkBoard(m, vector<int>(n, 0)); // m x n 벡터 초기화

    while (true) {

        for (int i = 0; i < board.size() - 1; i++) {

            for (int j = 0; j<board[0].size() - 1; j++) {

                if (board[i][j] == board[i][j + 1] && board[i][j] == board[i + 1][j] && board[i][j] == board[i + 1][j + 1] && board[i][j] != '.') {
                    checkBoard[i][j] = 1;
                    checkBoard[i][j + 1] = 1;
                    checkBoard[i + 1][j] = 1;
                    checkBoard[i + 1][j + 1] = 1;
                    count++;
                }

            }

        }

        if (count == 0)
            break;

        for (int i = 0; i < checkBoard.size(); i++) {

            for (int j = 0; j < checkBoard[0].size(); j++) {

                if (checkBoard[i][j] == 1) {
                    answer++;
                    checkBoard[i][j] = 0;
                    board[i][j] = '.';
                }

            }

        }

        for (int j = 0; j < n; j++) {

            for (int i = m - 2; i >= 0; i--) { // 세로로 거꾸로 탐색 (아래에서 두 번째 줄부터)

                if (board[i][j] != '.') { // 만약 점이 아니라면

                    for (int l = i; l < m - 1; l++) { // 바로 아래에 점이 있는지 확인하는 것을 반복(맨 아래로 내려갈 때 까지 or 점이 안나올 때 까지)

                        if (board[l + 1][j] == '.') { // 아래가 점이면

                            board[l + 1][j] = board[l][j]; // 한 칸을 내리고
                            board[l][j] = '.'; // 위를 점으로 바꾼다.

                        }
                        else { // 아래가 점이 아니면

                            break; // 아예 끝낸다 - 아래부터 위로 참고하기 때문에 아래가 점이 아니면 꽉 차있는 것이다.

                        }

                    }

                }

            }

        }

        count = 0;

    }

    return answer;
}