[프로그래머스 level2] 프렌즈4블록 (C++)

카카오 코딩테스트 [1차] 문제

 

2차원 배열의 원소가 떨어지는걸 구현하는게 핵심인 구현 문제이다.

 

문제에서 구현할 부분이 확실하게 나눠져 있음을 확인했다.

1. 2x2 블록을 모두 찾아서 지우기
2. 지워진 블록 떨어뜨리기

 

2x2블록을 찾아서 삭제하는 부분이다.

bool deleteBoard(){
    int del = 0;
    
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            if(!board_records[r][c]) continue;
            del += delete2x2(nboard[r][c], r, c);
        }
    }
    
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            if(board_records[r][c] == 2){
                board_records[r][c] = 0;
                nboard[r][c] = 0;
            }
        }
    }
    
    if(!del) return false;
    else{
        answer += del;
        return true;
    }
}

첫 번째 이중 for문을 돌면서 2x2 블록을 삭제한다. 삭제하면서 몇 개의 블록을 삭제했는지 확인하기 위해서 del 변수에 더해준다.

두 번째 이중 for문을 돌면서 삭제된 부분을 삭제 처리한다.

만약 지워진 블럭이 없다면 false를 리턴하고, 있다면 답을 갱신하고 true를 리턴한다.

 

 

이제 공중에 뜬 블럭들을 아래로 내려주는 작업이 필요하다.

void fall(){
    
    for(int c = 0; c < M; c++){
        int r = N-1;
        int vr = -1;
        
        while(r >= 0){
            if(board_records[r][c] == 0){
                vr = r;
            }
            while(vr != -1 && r >= 0){
                r--;
                if(nboard[r][c]){
                    nboard[vr][c] = nboard[r][c];
                    nboard[r][c] = 0;
                    board_records[r][c] = 0;
                    r = vr;
                    vr = -1;
                }
            }
            r--;
        }
    }
    
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            if(nboard[r][c]) board_records[r][c] = 1;
            else board_records[r][c] = 0;
        }
    }
}

0번째 열부터 M-1번재 열까지 순서대로 확인한다.

각 열에서는 N-1번째 행부터(가장 아래쪽 행) 0번째 행까지 확인한다.

중요한 부분은 행을 확인하는 부분이다.

1. 아래에서부터 올라가면서 비워진 부분을 체크한다. 
2. 비워진 부분이 체크되었고, 채워진 부분을 찾았다면(현재 위치) -> 비워진 부분에 현재 위치의 블럭을 옮겨주고, 현재 위치를 비워진 블럭으로 바꿔준다.
3. 행이 끝날때까지 반복하고, 열이 끝날때까지 반복한다.

 

 

최종 코드

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

using namespace std;

int N, M;
int answer = 0;

// 타일이 있으면 1, 타일이 없으면 0
// 타일이 있는데 이미 점수를 얻었으면 2
int board_records[31][31];
int nboard[31][31];

int dr[4] = {0, 0, 1, 1};
int dc[4] = {0, 1, 0, 1};

int delete2x2(int shape, int r, int c){
    // 지워진 타일의 개수를 반환
    if(r+1 == N || c+1 == M) return 0;
    
    int ret = 0;
    if(nboard[r+1][c]   == shape && 
       nboard[r][c+1]   == shape && 
       nboard[r+1][c+1] == shape){
        
        for(int k = 0; k < 4; k++){
            int nr = r + dr[k];
            int nc = c + dc[k];
            if(board_records[nr][nc] == 1){
                board_records[nr][nc] = 2;
                ret++;
            }
        }
    }
    
    return ret;
}

bool deleteBoard(){
    int del = 0;
    
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            if(!board_records[r][c]) continue;
            del += delete2x2(nboard[r][c], r, c);
        }
    }
    
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            if(board_records[r][c] == 2){
                board_records[r][c] = 0;
                nboard[r][c] = 0;
            }
        }
    }
    
    if(!del) return false;
    else{
        answer += del;
        return true;
    }
}

void fall(){
    
    for(int c = 0; c < M; c++){
        int r = N-1;
        int vr = -1;
        
        while(r >= 0){
            if(board_records[r][c] == 0){
                vr = r;
            }
            while(vr != -1 && r >= 0){
                r--;
                if(nboard[r][c]){
                    nboard[vr][c] = nboard[r][c];
                    nboard[r][c] = 0;
                    board_records[r][c] = 0;
                    r = vr;
                    vr = -1;
                }
            }
            r--;
        }
    }
    
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            if(nboard[r][c]) board_records[r][c] = 1;
            else board_records[r][c] = 0;
        }
    }
}

int solution(int m, int n, vector<string> board) {
    N = m;
    M = n;
    
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            nboard[r][c] = board[r][c] - 'A' + 1;
            if(nboard[r][c]) board_records[r][c] = 1;
        }
    }
    
    while(deleteBoard()){
        fall();
    }
    
    return answer;
}