[프로그래머스] 17679번 - 프렌즈4블록 (구현, 2018 KAKAO BLIND RECRUITMENT)

1. 문제 및 예제

 

 엄청난 구현 문제. 설계를 잘 하면 그렇게 어렵지 않게 해결할 수 있다. 중요한 점은 한 배열에서 사라질 모든 블럭을 찾아낸다는 것 같다. 블럭이 포함되어 있다는게 조금 까다로웠다.

---

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

프로그래머스

 

---

2. 풀이과정

 

 문제를 나눠보았다.

 

1. 블록을 터트리고 터진 블록의 갯수를 반환한다.

2. 터진 블록을 아래로 내린다.

 

 다음은 전체 코드이다.

 

#include <string>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

bool check_range(int r, int c, int max_r, int max_c){
    if(r < 0 || r >= max_r)
        return false;
    else{
        if(c < 0 || c >= max_c)
            return false;
        else
            return true;
    }
}

int count_blocks(int max_m, int max_n, vector<string> &bord, 
                 queue<pair<int, int>> &get_point){
    
    int blocks = 0;
    
    for(int i = 0; i < max_m - 1; i++){
        for(int j = 0; j < max_n - 1; j++){
            if(bord[i][j] != '0'){
                
                if(bord[i][j] == bord[i+1][j] && 
                   bord[i][j] == bord[i][j+1] && 
                   bord[i][j] == bord[i+1][j+1]){
                    
                    blocks += 4;    
                    get_point.push(make_pair(i,j));
                }
            }
        }  
    }
    return blocks;
}

void set_block(int max_m, int max_n, vector<string> &bord, queue<pair<int, int>> &get_point){
    
    while(!get_point.empty()){
        
        pair<int, int> buff = get_point.front();
        get_point.pop();
        
        int x = buff.first;
        int y = buff.second;
        
        bord[x][y]          = '0';
        bord[x + 1][y]      = '0';
        bord[x][y + 1]      = '0';
        bord[x + 1][y + 1]  = '0';   
    }
    
    for (int t = 0; t < max_m - 1; t++) {
        for (int i = 0; i < max_m - 1; i++) {
            for (int j = 0; j < max_n; j++) {
                if (bord[i][j] != '0' && bord[i + 1][j] == '0') {
                    char buff = bord[i][j];
                    bord[i][j] = bord[i + 1][j];
                    bord[i + 1][j] = buff;
                }
            }
        }
    }  
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    queue<pair<int, int>> get_point;
    
    int buff;
    while((buff = count_blocks(m, n, board, get_point)) != 0){
        set_block(m,n,board, get_point);
    }
    
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(board[i][j] == '0')
                answer++;
        }
    }
    
    return answer;
}

 

3. 결어

 

 구현은 연습밖에 없을 것 같다. 꾸준히 해야할 것 같다.