programmers [C++] : 2018 KAKAO BLIND RECRUITMENT 프렌즈 블록

programmers.co.kr/learn/courses/30/lessons/17679?language=cpp

코딩테스트 연습 - [1차] 프렌즈4블록

문제 설명

---

같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다

.

순서대로 ▶ 위 사진처럼 변형됩니다.

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미하고 입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하시면 됩니다.

 

접근 방식

---

문제에 주어지는 룰 그대로 코드를 작성해주시면 됩니다. ㅠㅠ 매번 말을 쉽지만 저는 그게 왜이리 어려울까요 ~

먼저 bfs로 4개의 사각형으로 이루어지는 구역들을 모두 컨테이너에 저장해놓습니다. 다음으로 bfs 단계에서 중복된 것은 제거해줍니다.

두번째로는 컨테이너에 해당되는 인덱스를 모두 삭제하고 이를 내려주는 작업을 진행합니다.

(원래 string으로 되어 있으므로 회전하여 공백을 넣어주고 사이즈를 줄인다음 다시 회전하여 복귀하려 했지만 ㅠㅠ 실패했습니다.)
내려주는 작업은 swap을 활용하여 루프를 돌면서 내려주었습니다. 다만 내려주는 작업이 없을시 옆 칸으로 이동할 수 있도록 flag를 설정해놓았습니다. 위 과정을 반복하면 완성됩니다.

 

코드

---

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
bool visit[31][31];
int dy[]={1,0,1};
int dx[]={0,1,1};
vector<pair<int,int> >ans;
int solution(int m, int n, vector<string> board) {
    int answer = 0;
    vector<pair<int,int> >v;
    int flag;
    while(true){
        flag=0;
        for(int i=0;i<m-1;i++){
            for(int j=0;j<n-1;j++){
                if(board[i][j]=='-')continue;
                for(int k=0;k<3;k++){
                    int ny=i+dy[k];
                    int nx=j+dx[k];
                    if(board[i][j]==board[ny][nx]){ 
                        v.push_back(make_pair(ny,nx));
                    }
                    else{
                        v.clear();break;
                    }
                }
                if(v.size()==3){
                    flag=1;
                    for(int a=0;a<v.size();a++)
                        ans.push_back(make_pair(v[a].first,v[a].second));
                    ans.push_back(make_pair(i,j));
                    v.clear();
                }
            }
        }
        if(flag==0)break;
        //삭제 및 내리기
        sort(ans.begin(),ans.end());
        ans.erase(unique(ans.begin(),ans.end()),ans.end());
        answer+=ans.size();
        for(int i=0;i<ans.size();i++){
            int y =ans[i].first;
            int x =ans[i].second;
            board[y][x]='-';
        }
        ans.clear();
        for(int i=0;i<n;i++){
            while(true){
                int chk=0;
                for(int j=1;j<m;j++){
                    if(board[j][i]=='-'){
                        if(board[j-1][i]!='-'){
                            swap(board[j][i],board[j-1][i]);
                            chk=1;
                        }
                    }
                }
                if(chk==0)break;
            }
        }
    }
    return answer;
}

funny algorithm 0_<