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

문제 바로가기

문제는 다 알고 있을테니...
우리가 해야하는건 2x2블록을 몇개 제거했는지 출력하는것이다.

접근 방식

어떻게 풀어나갈지 단계를 짜보자.

1. 2 x 2 블록들을 찾고 해당 블록들의 좌표(왼쪽 위의, 즉 2사분면 좌표)값들을 반환해주자.
2. 1 단계에서 나온 좌표값들을 통해 2 x 2블록들을 제거해주자, 제거함과 동시에 개수도 세주자
3. 빈칸 위에 있는 블록들 아래로 내려주기
4. 1~3 과정 반복
5. 1 단계에서 더 이상 좌표값을 반환해주지 않는다면 반복 끝

바로 코드 갑니다.

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

using namespace std;
struct Mypair{int x,y;};
int times; // 제거되는 블록 개수가 담길 변수

//2x2 블록 찾아서 해당 좌표 리턴
vector<Mypair> findFourBlock(int a, int b, vector<string> &c){
    vector <Mypair> axis;
    for(int i = 0; i < a - 1; i++){
        for(int j = 0; j < b - 1; j++){
            if(c[i][j] != '#' && (c[i][j] == c[i][j+1] 
            && c[i][j+1] == c[i+1][j+1] && c[i+1][j] == c[i+1][j+1])){
                Mypair pos;
                pos.x = i;
                pos.y = j;
                axis.push_back(pos);
            }
        }
    }
    return axis;
}

//2x2 블록들 제거!! 동시에 개수도 세준다
void deleteBlock(vector<string> &a, vector<Mypair> &b){
    for(int i = 0; i < b.size(); i++){
        if(a[b[i].x][b[i].y] != '#') {a[b[i].x][b[i].y] = '#'; times++;}
        if(a[b[i].x][b[i].y+1] != '#') {a[b[i].x][b[i].y+1] = '#'; times++;}
        if(a[b[i].x+1][b[i].y] != '#') {a[b[i].x+1][b[i].y] = '#'; times++;}
        if(a[b[i].x+1][b[i].y+1] != '#') {a[b[i].x+1][b[i].y+1] = '#'; times++;}
    }
}

//빈칸위의 블록들 아래로 내려주기
void cleanBlank(int a, int b, vector<string> &c){
    for(int i = a-1; i > 0; i--){
        for(int j = b-1; j >= 0; j--){
            if(c[i][j] == '#'){
                for(int k = i-1; k >= 0; k--){
                    if(c[k][j] != '#'){
                        swap(c[i][j],c[k][j]);
                        break;
                    }
                }
            }
        }
    }
}
int solution(int m, int n, vector<string> board) {
    while(1){
        vector<Mypair> blist = findFourBlock(m,n,board);
        if(blist.size() == 0 ) break; //더 이상 반환해줄 좌표가 없다면 반복 끝
        deleteBlock(board,blist);
        cleanBlank(m,n,board);
    }
    return times;
}

일반적인 구현 문제이다. 알고리즘 시작한지 1년도 안되었지만
구현 = 노가다 같다.