[BAEKJOON] 2933 미네랄 (C++)

[문제]

간단한 BFS구현문제 라고 생각했지만, 미네랄 클러스터를 이해하는데 시간을 많이썻었다.

[조건]

1. 좌, 우에서 막대기를 던질때, 미네랄이 있으면 파괴된다.

2. 미네랄이 파괴된후, 새로운 클러스터가 생성되었을 때 공중에 떠있다면

   미네랄 클러스터나 바닥에 닿기전까지 계속해서 떨어진다. 다른 미네랄클러스터를 만나게된다면 합쳐진다.

3. 주어진 막대회수만큼 반복한다

[해결순서]

순서에 따라 방향에맞춰 막대기를 던지고, 그 위치에서 처음만나는 미네랄을 파괴시키면된다.

공중에 떠있는 미네랄 클러스터를 판별하는 방법이 중요한데,

바닥에 붙어있는 미네랄을 기점으로 BFS를 돌려 Check해주고

Check되지않은 미네랄 클러스터가 존재할 시에 [조건2]를 구현해주면 된다.

[주의할점]

미네랄 클러스터는 한꺼번에 떨어지게된다.

맨처음 구현할 때 개별적이라 생각하여, 각 미네랄 클러스터 Line을 Stack에 저장하고 [조건2]에 해당하도록 구현했었다.

[두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다]는 경우를 깊게생각안했더게 흠이었음.

[부분소스코드]

미네랄이 떨어지는것 구현하는게 키포인트

공중에 떠있는 미네랄 클러스터의 각 {y, x}좌표를 벡터에 추가시키고

전체적으로 한칸내린 좌표들을 다음벡터에 저장하고 순환하는코드로 구성했다.

미네랄이있거나 범위를 벗어나는경우 해당 좌표들을 x로 다시채워줌[ setcluster() ]으로서 코드는 마무리된다.

vector<Data> fall(vector <Data> &v) {
    while (true) {
        vector <Data> next;
        next = v;
        v = vector<Data>();
        for (int i = 0; i < next.size(); i++) {
            int ny = next[i].y + 1;
            int nx = next[i].x;
            if (!range(ny, nx) || check[ny][nx])
                return next;
            else
                v.push_back({ ny, nx });
        }
    }
}

[전체소스코드]

#ifdef _DEBUG
#include "bits_stdc++.h"
#else
#include "bits/stdc++.h"
#endif
#pragma warning(disable:4996)
using namespace std;

#define MAX 105
char cluster[MAX][MAX];
bool check[MAX][MAX];

int h, w, bar;
int yY[] = { -1,1,0,0 };
int xX[] = { 0,0,-1,1 };

typedef struct data {
    int y;
    int x;
}Data;
bool range(int y, int x) {
    if (y<0 || x<0 || y>h - 1 || x>w - 1)
        return false;
    else
        return true;
}
void setcluster(vector <Data> v) {
    for (int i = 0; i < v.size(); i++)
        cluster[v[i].y][v[i].x] = 'x';
}
vector<Data> fall(vector <Data> &v) {
    while (true) {
        vector <Data> next;
        next = v;
        v = vector<Data>();
        for (int i = 0; i < next.size(); i++) {
            int ny = next[i].y + 1;
            int nx = next[i].x;
            if (!range(ny, nx) || check[ny][nx])
                return next;
            else
                v.push_back({ ny, nx });
        }
    }
}
void find() {
    bool search = false;
    memset(check, 0, sizeof check);
    queue <Data> q;
    for (int i = 0; i < w; i++) {
        if (cluster[h - 1][i] == 'x' && !check[h-1][i]) {
            q.push({ h - 1, i });
            check[h - 1][i] = true;
            while (!q.empty()) {
                Data out = q.front(); q.pop();
                for (int k = 0; k < 4; k++) {
                    int ny = out.y+yY[k];
                    int nx = out.x+xX[k];
                    if (range(ny, nx) && !check[ny][nx] && cluster[ny][nx] == 'x') {
                        check[ny][nx] = true;
                        q.push({ ny, nx });
                    }
                }
            }
        }
    }
    vector <Data> v;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            if (cluster[i][j] == 'x' && !check[i][j]) {
                cluster[i][j] = '.';
                v.push_back({ i,j });
                search = true;
            }
    if (search) {
        vector <Data> change = fall(v);
        setcluster(change);
    }
}
void broke(int shoot, bool flag) {
    if (flag == 0) {
        for (int i = 0; i < w; i++) {
            if (cluster[shoot][i] == 'x') {
                cluster[shoot][i] = '.';
                find();
                return;
            }
        }
    }
    else {
        for (int i = w-1; i >= 0; i--) {
            if (cluster[shoot][i] == 'x') {
                cluster[shoot][i] = '.';
                find();
                return;
            }
        }
    }
}
int main() {
#ifdef _CONSOLE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> h >> w;
    for (int i = 0; i < h; i++)
        cin >> cluster[i];
    cin >> bar;
    int shoot;
    for (int i = 0; i < bar; i++) {
        cin >> shoot;
        broke(h-shoot, i%2);
    }
}