프로그래머스 프렌즈4마블

아이디어

• 시뮬레이션을 구현할 줄 안다

접근방식

1. do-while문을 통해 제거할 블록이 없을때 까지 계속 돌린다. 제거할 블록이 있으면 bool 변수를 false로 만들어 계속 반복문을 실행시킨다
2. 2중 for문을 돌며 '-'(제거된 블록) 이 아니라면 4블록을 검사해, 모두 같다면 제거해준다, 제거해주면서 answer를 증가시켜 준다.
3. 2중 for문을 돌며 제거한 블록을 기준으로 아래로 내려준다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;
int dy[3] = {0,1,1};
int dx[3] = {1,0,1};
vector<string> new_board;
//칸4개 삭제해야함? 하면 true
bool remove_check(int row, int col){
    char now_c = new_board[row][col];
    
    for(int i=0;i<3;i++){
        int next_row = row+dy[i];
        int next_col = col+dx[i];
        if(next_col >= new_board[0].size() || next_row >= new_board.size()) return false;
        char next_c = new_board[next_row][next_col];
        if(next_c != now_c) return false;
    }
    return true;
}

// '-' 추가하기
int remove_swap(int row, int col, vector<string> &temp_board){
    int cnt = 0;
    if(temp_board[row][col] != '-'){
        temp_board[row][col] = '-';
        cnt++;
    }
    for(int i=0;i<3;i++){
        int next_row = row+dy[i];
        int next_col = col+dx[i];
        if(temp_board[next_row][next_col] != '-'){
            temp_board[next_row][next_col] = '-';
            cnt++;
        }
    }
    
    return cnt;
}

//아래로 내리기, 맨위가 0, 아래가 temp_board.size()-1
void put_down(int row,int col, vector<string> &temp_board){
    for(int i = row; i >= 1 ; i--){
        temp_board[i][col] = temp_board[i-1][col];
    }
    temp_board[0][col] = '-';
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    new_board = board;
    
    bool is_done = true;
    
    do{
        is_done = true;
        vector<string> temp_board = new_board;
        
        for(int row=0;row<temp_board.size();row++){
            for(int col=0;col<temp_board[0].size();col++){
                if(new_board[row][col]!= '-'){
                    bool have_to_remove = remove_check(row,col); //remove check
                    if(have_to_remove == true){
                        int temp = remove_swap(row,col,temp_board);  //'-'로 바꾸기
                        answer+= temp;
                        is_done = false;
                    }
                }
            }
        }
        
        for(int row=0;row<temp_board.size();row++){
            for(int col=0;col<temp_board[0].size();col++){
                if(temp_board[row][col] == '-'){
                    put_down(row,col,temp_board); // 아래로 내리기
                }
            }
        }
        
        new_board=temp_board;
        
    }while(is_done ==false);
    
    return answer;
}

평가

시뮬레이션을 차근차근 한다면 정말 쉬운문제.
정말 쉬운 문제이지만 이 문제는 굉장히 푸는데 오래걸렸습니다.
저는 어떻게하면 조금 더 효율적으로 짤 수 있을까 생각하며 풀었지만,
실제 풀이는 그냥 반복문을 계속 돌면서 이중 for문까지 사용해도 시간복잡도가 충분한 문제였습니다.
때로는 입력 범위가 작고 시뮬레이션 문제라면 생각 나는걸 바로 풀 필요가 있을 것 같습니다.

또한, 다른 분들의 풀이를 통해, 각 기능을 함수로 나눠서 구현하면 알아보기가 편하다는 점을 굉장히 많이 느꼈습니다. 앞으로 이런식으로 사용하는 연습을 많이 해야할 것 같습니다.

• 배울 것
  1) 시뮬레이션은 입력 범위가 작으면, 간단하게 구현해보자
  2) 알고리즘의 기능을 최대한 함수로 나눠서 표현하자!! (알아보기가 굉장히 쉽다)