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

 

Level. 2

 

문제

 

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

 

 

 

풀이

#include <string>
#include <vector>
#include <algorithm> // swap()
#include <iostream>

using namespace std;

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

int solution(int m, int n, vector<string> board) {
    int answer = 0, count = 0;
    vector<vector<pair<char, bool>>> v(m); // 블럭과 블럭의 존재유무 
    
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            v[i].push_back({board[i][j], true});
        }
    }
    
    while(true){
        // 1. 4개의 블럭 체크
        for(int i=0; i<m-1; i++){
            for(int j=0; j<n-1; j++){
                if(v[i][j].first   == v[i+1][j].first and
                   v[i][j].first   == v[i][j+1].first and 
                   v[i+1][j].first == v[i+1][j+1].first){
                    v[i][j].second     = false;
                    v[i+1][j].second   = false;
                    v[i][j+1].second   = false;
                    v[i+1][j+1].second = false;
                    
                }
            }
        }
        
        count = 0;
        // 2. 블럭 삭제
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(!v[i][j].second and v[i][j].first != ' '){
                    v[i][j].first = ' ';
                    count += 1;
                }
            }
        }
        if(count == 0) break;
        answer += count;

        // 3. 맵 업데이트
        for(int i=m-1; i>0; i--){
            for(int j=0; j<n; j++){
                if(v[i][j].first == ' ' and !v[i][j].second){
                    int row = i;
                    while(row>0){
                        row--;
                        if(v[row][j].second) break;
                    }
                    swap(v[i][j], v[row][j]);
                } 
            }
        }
        cout << endl;
    }
    
    
    return answer;
}

 

해결방법

1.  판 크기의 배열을 만들어 [블럭의종류, flag값(default = true)] 를 저장한다.
2.  판을 탐색하며 4개의 블록이 붙어있을 경우 해당 블럭 모두 flag값을 false로 변경한다. 
3.  블록의 종류가 공백이 아니고, false값을 가지고 있는 블럭의 경우, 사라져야한 블럭이므로 블럭의 종류를 ' ' 로 만들어 제거한다.
    이때 제거된 개수만큼 count에 +1을 해준다.
4.  count에 변화가 없을 경우 더 이상 사라질 블록이 없다는 의미이므로 탐색을 종료한다. 
5.  맵을 업데이트 하여 빈 공간을 메우도록 한다. 

 

 

---

다른 풀이

#include <string>
#include <vector>

using namespace std;

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

    while(1){
        bool isDone = true;
        vector<vector<bool>> check;
        check.resize(m);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){  
                check[i].push_back(false);
            }
        }
        for(int i=0;i<m-1;i++){
            for(int j=0;j<n-1;j++){
                if(board[i][j] == 0) continue;
                if(board[i][j] == board[i][j+1]){
                    char target = board[i][j];
                    if((board[i+1][j] == target) && (board[i+1][j+1] == target)){
                        check[i][j] = true;
                        check[i][j+1] = true;
                        check[i+1][j] = true;
                        check[i+1][j+1] = true;
                        isDone = false;
                    }
                }
            }
        }

        if(isDone == true) break;

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(check[i][j] == true){
                    answer++;

                    for(int k=i;k>0;k--){
                        board[k][j] = board[k-1][j];
                    }
                    board[0][j] = 0;
                }
            }
        }
    }

    return answer;
}

 

맵을 업데이트 하는 방식이 다르다.

위 코드는 블록을 제거하면서 곧바로 맵을 업데이트 한다. 

---

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

프로그래머스