[프로그래머스 Level2] [1차] 프렌즈4블록 - C언어(C++) - 2018 KAKAO BLIND RECRUITMENT

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

프로그래머스

문제 설명

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

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

 

 

 

---

조금 헷갈릴 수 있으나 실제 사용되는 게임이고 괜찮은 문제였던 것 같다.

다음은 구현한 코드 중 각 주요 기능에 대한 세부 설명이다.

 

 

for (int i = 0; i < m; i++) {  
            for (int j = 0; j < n; j++) {
                if (i+1==m || j+1==m || map[i][j]==' ') continue;
                if (map[i][j]==map[i][j+1] && map[i][j]==map[i+1][j] &&
                        map[i][j]==map[i+1][j+1]) {
                    v.push_back({i,j});
                }
            }
        }     
        if (v.empty())
            break;

지워질 수 있는 2*2 블록을 찾는 과정이다. map의 모든 행과 열을 탐색하다가 해당 위치의 오른쪽, 아래, 대각선 오른쪽에 있는 블록들의 값이 모두 같다면 벡터에 행렬 위치를 넣었다.

작업 수행이 끝나는 것은 위 코드를 진행했음에도 벡터에 아무것도 들어가지 않았을 때(더 이상 지워질 블록이 없을 때)이다.

 

 

for (int i = 0; i < v.size(); i++) {
            int y = v[i].first;
            int x = v[i].second;
            map[y][x]=map[y][x+1]=map[y+1][x]=map[y+1][x+1]=' ';
        }

지워질 수 있을 것이라 찾은 모든 2*2 블록들을 지우는 과정이다. 이 포인트를 주의해야한다고 생각한다. 2*2 블럭모양은 겹쳐질 수 있는데, 그렇기 때문에 한 게임당 지워질 수 있는 2*2블럭들을 표시해두고 이후 한 번에 지워질 수 있는 블럭들을 삭제한 후 위쪽 블럭들을 아래로 내리는 작업을 수행하여야한다.

 

 

for (int i = 0; i < v.size(); i++) {
            int y = v[i].first;
            int x = v[i].second;
            
            if (y == 0) continue;
            int y_uIdx1 = y + 1; 
            int y_uIdx2 = y + 1; 
            int y_dIdx1 = y + 1; // 가장 밑에 있는 빈 칸의 행 인덱스
            int y_dIdx2 = y + 1; // 가장 밑에 있는 빈 간의 행 인덱스
            while (map[y_uIdx1][x] == ' ') y_uIdx1--; // 가장 밑에 있는 블록의 행 인덱스
            while (map[y_uIdx2][x+1] == ' ') y_uIdx2--; // 가장 밑에 있는 블록의 행 인덱스
            
            for (int j = y_uIdx1; j >= 0; j--) 
                swap(&map[j][x], &map[y_dIdx1--][x]);
            for (int j = y_uIdx2; j >= 0; j--)
                swap(&map[j][x+1], &map[y_dIdx2--][x+1]);
        }

지워진 블록 위에 있는 블록들을 아래로 떨어트리는 과정이다. 다른 구현 포인트들보다 이 부분의 수정을 계속해서 반복했고 많이 헷갈렸다. 여러 방법이 있을 지도 모르나, 우선 나는 y = 0, 즉 map배열의 가장 위에 있는 2*2블록이 지워진 경우에는 지워진 블록위의 블록이 없으므로 코드를 continue 처리하였다. 그 후, 최대한 밑에 있는 빈 칸의 행 인덱스와 최대한 밑에 있는 블록의 행 인덱스를 찾았다. 찾아진 인덱스들을 이용하여 블록들을 아래로 떨어트리기 위해 가장 밑 빈 칸 위치와 가장 밑 블록 위치를 서로 교환하였다.

 

 

 

<< 전체 코드 >>

#include <string>
#include <vector>

using namespace std;

void swap(char* a, char* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

char map[30][30];

int solution(int m, int n, vector<string> board) {
    // 2차원 배열에 board 한 줄 내 문자 요소 하나씩 넣기
    for (int i = 0; i < m; i++) 
        for (int j = 0; j < n; j++)
            map[i][j] = board[i][j];
    
    vector<pair<int,int>> v;
    while(1) {
        // 지워질 수 있는 2*2 블록 찾기
        v = vector<pair<int,int>>();
        for (int i = 0; i < m; i++) {  
            for (int j = 0; j < n; j++) {
                if (i+1==m || j+1==m || map[i][j]==' ') continue;
                if (map[i][j]==map[i][j+1] && map[i][j]==map[i+1][j] &&
                        map[i][j]==map[i+1][j+1]) {
                    v.push_back({i,j});
                }
            }
        }     
        if (v.empty())
            break;
        
        // 지워질 수 있는 모든 2*2 블록 지우기
        for (int i = 0; i < v.size(); i++) {
            int y = v[i].first;
            int x = v[i].second;
            map[y][x]=map[y][x+1]=map[y+1][x]=map[y+1][x+1]=' ';
        }
        
        // 위에 있는 블록 떨어트리기
        for (int i = 0; i < v.size(); i++) {
            int y = v[i].first;
            int x = v[i].second;
            
            if (y == 0) continue;
            int y_uIdx1 = y + 1; 
            int y_uIdx2 = y + 1; 
            int y_dIdx1 = y + 1; // 가장 밑에 있는 빈 칸의 행 인덱스
            int y_dIdx2 = y + 1; // 가장 밑에 있는 빈 간의 행 인덱스
            while (map[y_uIdx1][x] == ' ') y_uIdx1--; // 가장 밑에 있는 블록의 행 인덱스
            while (map[y_uIdx2][x+1] == ' ') y_uIdx2--; // 가장 밑에 있는 블록의 행 인덱스
            
            for (int j = y_uIdx1; j >= 0; j--) 
                swap(&map[j][x], &map[y_dIdx1--][x]);
            for (int j = y_uIdx2; j >= 0; j--)
                swap(&map[j][x+1], &map[y_dIdx2--][x+1]);
        }
    }
    
    // 지워진 블록의 개수 구하기
    int erasedCnt = 0;
    for (int i = 0; i < m; i++) 
        for (int j = 0; j < n; j++)
            if (map[i][j] == ' ')
                erasedCnt++;
    
    return erasedCnt;
}