[2017 카카오 코딩테스트] 프렌즈4블록

분류 

시뮬레이션

요구사항

1. 4개가 뭉쳐서 crush되는 곳 찾기

2. crush되어진 다음 밑으로 이동

풀이

1. 4개가 뭉쳐서 crush되는 곳 찾기

-> 전체 map을 탐색하면서 4개가 뭉쳐있는 곳을 체크해주고, 없애준다

2. crush되어진 다음 밑으로 이동

-> 없어진 곳은 deque를 이용하여서 밑에서부터 채워준다

3. 정답 출력

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <string.h>
#include <algorithm>
#include <deque>
//#include <map>
 

using namespace std;
vector<string> map={"TTTANT","RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"};
char mymap[31][31];
int dr[3] = {0,1,1};
int dc[3] = {1,0,1};
int visit[31][31];
int n;
int m;
int ans=0;
bool check(){
    int flag=0;
    memset(visit,0,sizeof(visit));
    for(int i=0 ; i < n ; i++){
        for(int j=0 ; j < m ; j++){
            char now=mymap[i][j];
            if(now==0) continue;
            int cntflag=0;
            for(int k=0 ; k<3 ; k++){
                int r = i+dr[k];
                int c = j+dc[k];
                if(r>=n || c>=m) continue;
                if(mymap[r][c] ==now){
                    cntflag++;
                }
            }
            if(cntflag==3){
                flag=1;
                visit[i][j]=1;
                for(int k=0 ; k<3 ; k++){
                    int r = i+dr[k];
                    int c = j+dc[k];
                    visit[r][c]=1;
                    
                }   
            }
        }
    }
    if(flag==0) return false;
    return true;
}
void erase(){
    for(int i=0 ; i < n ; i++){
        for(int j=0; j< m ; j++){
            if(visit[i][j]==1){
                visit[i][j]=0;
                mymap[i][j]=0;
                ans++;
            }
        }
    }
}
void clean(){
    deque<char> dq;
    for(int i=0 ; i < m ; i++){
        for(int j =n-1 ; j >=0 ; j--){
            if(mymap[j][i]==0) continue;
            if(mymap[j][i] !=0){
                dq.push_back(mymap[j][i]);
                mymap[j][i]=0;
            }
        }
        int r=n-1;
        int c=i;
        while(!dq.empty()){
            mymap[r][c] = dq.front();
            dq.pop_front();
            r--;
        }
 

    }
}
int main(){
    n=map.size();
    m= map[0].size();
    for(int i =0 ; i <n ; i++){
        for(int j=0 ; j <m ; j++){
            mymap[i][j]=map[i][j];
            cout<<mymap[i][j];
        }
        cout<<endl;
    }
    int cnt=0;
    while(true){
        if(check()){
            erase();
            clean();
        }
        else{
            break;
        }
        cnt++;
        if(cnt==3)
            break;
    }
    cout<<ans<<endl;
 

}