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

[문제]

프렌즈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가 사용된다.

출력 형식

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

입출력 예제

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개의 블록이 지워진다.

[풀이]

 

1. 어려운 문제였습니다. 혼자 해결을 못해서 (https://jay-ji.tistory.com/13?category=732905) 도움을 얻어서 풀 수 있었다. 

 

2. SWEA에 비슷한 문제인 벽돌깨기와 비슷하다는 생각을 했다.

2019/08/29 - [SWEA/미해결 모음 ] - [SWEA] 벽돌깨기

[SWEA] 벽돌깨기

 

3. 보드를 탐색하면서 나를 기준으로 아래쪽, 오른쪽, 오른쪽 대각선 아래쪽이 나와 동일한 영문자를 가지고 있다면 2*2 블록에 해당된다. 

터트릴 블록이 있으므로 answer++을 해준다. 

대문자인 블록들을 소문자로 바꾸어서 터트릴 블록이라는 것을 표시한다. (다른 문자로 바꿔버리거나 없애버리면 그 밑 혹은 옆의 블록을 탐색할 때 기준이 없어져버리니 toupper 함수를 통해 쉽게 비교할 수 있도록 한다.)

터트릴 블록이 있다면 flag = true 로 만들어준다. (do -while 을 사용해서 적어도 한 번은 블록을 탐색할 수 있도록 했다.)

 

4. flag == true라면 블록을 터트렸다는 것이기 때문에 아래에 공백 또는 소문자가 있다면 밑으로 블록들을 끌어내려준다. 

이 문제의 핵심 포인트인 것 같다. 

 

---

#include <string>
#include <vector>
 
using namespace std;
 
//대소문자 상관없이 같은지 확인하기 위한 메소드
int cmpChar(char a, char b) {
    if (isupper(a) && isupper(b) && a == b) return 1;
    if (!isupper(a) && isupper(b) && toupper(a) == b) return 1;
    if (isupper(a) && !isupper(b) && a == toupper(b)) return 1;
    if (!isupper(a) && !isupper(b) && a == b) return 1;
    
    return 0;
}
 
int solution(int m, int n, vector<string> map) {
    int answer = 0;
    
    bool flag = false;
    
    do {
        //적어도 한 번은 탐색을 해야하기 때문에 do-while로 설정함 
        flag = false;
        
        //2*2는 나를 기준으로 오른쪽, 아래쪽, 대각선 아래쪽으로 구성된다. 
        for (int i = 0; i < m-1; i++) {
            for (int j = 0; j < n-1; j++) {
                if (map[i][j] != ' ' && cmpChar(map[i][j], map[i+1][j]) &&cmpChar(map[i][j], map[i][j+1]) && cmpChar(map[i][j], map[i+1][j+1]) ) {
                    //대문자일 경우 터트릴 블록 
                    //소문자로 바꾸어서 터트릴 것이라는 걸 표시한다. 
                    //완전 다른 문자로 바꾸어버리면 크로스에 포함되는 블록을 알 수 없어진다. 
                    if (isupper(map[i][j])) {
                        map[i][j] += 32;
                        answer++;
                    }
                    if (isupper(map[i+1][j])) {
                       map[i+1][j] += 32;
                        answer++;
                    }
                    if (isupper(map[i][j+1])) {
                        map[i][j+1] += 32;
                        answer++;
                    }
                    if (isupper(map[i+1][j+1])) {
                        map[i+1][j+1] += 32;
                        answer++;
                    }
                    flag = true; //하나라도 터트릴 블록이 생김 -> 터트릴 블록이 더 이상 없다면 탐색 중지 
                }
            }
        }
        
        if (flag) {
            //아래로 끌어내려 준다. 
            for (int i = 0;  i < n; i++) {
                for (int j = m-2; j >= 0; j--) {
                    //공백이나 소문자가 없을때까지 내려준다. 
                    for (int k= j; k < m-1; k++) {
                        //아래를 살펴보면서 공백이나 소문자가 있는지 확인 
                        if (map[k+1][i] == ' ' || !isupper(map[k+1][i])) {
                            map[k+1][i] = map[k][i];
                            map[k][i] = ' ';
                        }
                    }
                }
            }
        }
        
    } while(flag);
    return answer;
}