"2018 KAKAO BLIND RECRUITMENT" > [1차] 프렌즈4블록

문제: programmers.co.kr/learn/courses/30/lessons/17679

 

<조건>

• 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
• 2 ≦ n, m ≦ 30
• board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.
• 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는다.
• 블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.
• 만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

 

문제 풀이:

1. 먼저 전체 판을 스캔하면서, 2x2가 같은 모양은 블록을 찾고, 이를 blocks 변수에 넣는다.
   1. set<pair<int,int>> blocks;
   2. set을 사용한 이유는, 오른쪽 예제와 같이 중복되는 부분이 있기 때문
   3. set의 사이즈가 제거될 블록의 수와 같으므로 answer에 더해준다.
2. 다음은, set에 저장된 block들을 지울 함수를 만든다.
   1. removeBlock()
   2. 해당 칸들을 모두 '.'로 바꾼다.
3. 그리고, 지워진 공간을 채울 함수를 만든다.
   1. moveBlock();
   2. 세로로 밑에서부터 보면서, 위에 블록들을 당겨준다. 
   3. 빈 공간을 찾기 위해 맨 밑에서부터 curx를 마이너스해가며 올라간다.
   4. curx가 가리키는 곳이 빈 공간이라면('.') newx변수를 이용해 해당 줄에서 빈칸이 아닌 가장 아래 블록(curx 위쪽으로)을 찾아 swap 해준다.
4. 1~3번 과정을 반복한다.
   1. 1번 과정을 수행 후, set이 비어있다면 더 이상 제거할 블록이 없다는 뜻으로 작업을 종료한다.

 

 

* 추가

맞게 구현했다고 생각하고 코드 실행시켰더니 segmentation fault가 났다.

"왜지...?"하면서 코드 한 줄 한 줄 다시 봤는데 removeBlock() 반환형을 bool로 해놓아서 그런거였다 ㅠㅠㅠ

(반환형 bool인데 아무것도 반환 안 해서) 

 

 

 

 

소스 코드:

#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

typedef pair<int,int> P;
set<P> blocks;
vector<string> newBoard;

void removeBlock(){
    for(P block: blocks){
        newBoard[block.first][block.second]='.';
    }
}
void moveBlock(int n,int m){

    for(int i=0;i<n;i++){
        int curx=m-1;
        int newx=m-2;
        while(newx>=0){
            if(newBoard[curx][i]=='.'){
                if(newBoard[newx][i]!='.'){
                    newBoard[curx][i]=newBoard[newx][i];
                    newBoard[newx][i]='.';
                    curx--;
                }
                newx--;
            }
            else curx--;
            
            if(newx>=curx) newx=curx-1;
        }
    }
}
int solution(int m, int n, vector<string> board) {
    int answer = 0;
    newBoard = board;
    while(1){
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i+1>=m||j+1>=n) continue;

                char f = newBoard[i][j];
                if(f!='.'&&newBoard[i+1][j]==f &&newBoard[i+1][j+1]==f&&newBoard[i][j+1]==f){
                    blocks.insert({i,j});
                    blocks.insert({i+1,j});
                    blocks.insert({i,j+1});
                    blocks.insert({i+1,j+1});
                }
             }
        }
        if(blocks.size()==0) break;
        answer+=blocks.size();
        
        removeBlock();
        moveBlock(n,m);
        
        blocks.clear();
    }
    
    return answer;
}