[BOJ] 11559 : 뿌요 뿌요

12101 : 뿌요 뿌요

풀이

시뮬레이션

19년3월삼성SW테스트 A형 유사문제.

삼성인재개발원에서 풀었는데, 2시간20분동안 반례와 싸우다가 못풀고 나왔었다.

물론 그문제는 여러 조건이 더있어서 이문제 보다 어려웠다.

하지만 핵심 기능인 탐색과 내리는 부분이 상당히 유사하다.

탐색은 BFS로 구현했고,

끌어내리는 코드는 while문으로 p,q가 포인터를 짚어가며 옮겨주는 방식으로 풀었다.

저번에 2048문제에서도 이렇게 내려주는것을 짰었기 때문에 신뢰도 높게 짤수 있었다.

상시테스트 시험장에서도 이렇게 짰으면 바로 통과했을것 같다.

코드

#include <iostream>
#include <queue>
#include <deque>
#include <vector>
#include <cstring>
#include <functional>
using namespace std;
//'.' R G B P Y
char arr[12][6];
int chk[12][6];

const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

//아래에 .이 있다면 밑으로 내려주자
void gravity() {
    for (int i = 0; i < 6; i++) {
        int p = -1;
        int q = 11;
        while (q >= 0) {
            if (p==-1 && arr[q][i] == '.') {
                p = q;
            }
            else if (p!=-1 && arr[q][i] != '.') {
                arr[p][i] = arr[q][i];
                arr[q][i] = '.';
                q = p;
                p = -1;
            }
            q--;
        }
    }
}

//4개이상 연결되어있으면 .으로 바꿔주자
bool bfs() {
    memset(chk, 0, sizeof(chk));
    vector<pair<int, int>> eraseList;
    bool result = true;
    for (int i = 0; i < 12; i++) {
        for (int j = 0; j < 6; j++) {
            if (arr[i][j] != '.' && chk[i][j] == 0) {
                char color = arr[i][j];
                chk[i][j] = 1;
                queue<pair<int, int>> q;
                vector<pair<int, int>> v;
                q.push({i,j});
                v.push_back({ i,j });
                while (!q.empty()) {
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();
                    for (int dir = 0; dir < 4; dir++) {
                        int nx = x + dx[dir];
                        int ny = y + dy[dir];
                        if (nx >= 0 && nx < 12 && ny >= 0 && ny < 6) {
                            if (chk[nx][ny] == 0 && arr[nx][ny] == color) {
                                q.push({nx,ny});
                                v.push_back({nx,ny});
                                chk[nx][ny] = 1;
                            }
                        }
                    }
                }
                if (v.size() >= 4) {
                    for (auto x : v) {
                        eraseList.push_back(x);
                    }
                    result = false;
                }
            }
        }
    }
    for (auto x : eraseList) {
        arr[x.first][x.second] = '.';
    }
    //1개라도 터지면 false리턴
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    for (int i = 0; i < 12; i++) {
        for (int j = 0; j < 6; j++) {
            cin >> arr[i][j];
        }
    }
    int ans = 0;
    while (1) {
        bool flag = bfs();
        if (flag) {
            break;
        }
        gravity();
        ans++;
    }
    cout << ans;
    return 0;
}
Written on April 12, 2019