미네랄

https://www.acmicpc.net/problem/2933

2933번: 미네랄

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<utility>
 
using namespace std;
 
int r, c, n;
string map[100];
int d[100][100][100];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
vector<int> spear;
 
void crush(int h, int dir) {
    int height = r - h;
    if (dir % 2 == 0) {
        for (int i = 0; i < c; i++) {
            if (map[height][i] == 'x') {
                map[height][i] = '.';
                break;
            }
        }
    }
    else {
        for (int i = c - 1; i >= 0; i--) {
            if (map[height][i] == 'x') {
                map[height][i] = '.';
                break;
            }
        }
    }
}
 
vector<pair<int, int> > cluster(int x, int y, int cnt,int io) {
    queue<pair<int, int> > q;
    vector<pair<int, int>> v;
    q.push({ x,y });
    v.push_back({ x,y });
    d[x][y][io] = cnt;
    bool ground = false;
    while (!q.empty()) {
        x = q.front().first; y = q.front().second;
        q.pop();
        if (!ground && x == r - 1) {
            ground = true;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i]; int ny = y + dy[i];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            if (map[nx][ny] == 'x' && d[nx][ny][io] == 0) {
                d[nx][ny][io] = cnt;
                v.push_back({ nx,ny });
                q.push({ nx,ny });
            }
        }
    }
    if (ground) {
        v.clear();
    }
    return v;
}
 
void print() {
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cout << map[i][j];
        }cout << '\n';
    }
}
 
void down(vector<pair<int, int>> & clu,int idx, int value) {
    bool on = false;
    for (int i = 0; i < clu.size(); i++) {
        map[clu[i].first][clu[i].second] = '.';
    }
    while (true) {
        for (int i = 0; i < clu.size(); i++) {
            int x = clu[i].first; int y = clu[i].second;
            if (x + 1 == r || (d[x + 1][y][idx] != 0 && d[x + 1][y][idx] != value))
            {
                //cout << x + 1 << ' ' << y << '\n';
                on = true;
                break;
            }
        }
        if (on) break;
        for (int j = 0; j < clu.size(); j++) {
            clu[j].first = clu[j].first + 1;
            //cout << "HELLO" << '\n';
        }
    }
    for (int i = 0; i < clu.size(); i++) {
        map[clu[i].first][clu[i].second] = 'x';
    }
    
 
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        cin >> map[i];
    }
    cin >> n;
    for (int i = 0; i < n; i++) {
        int s;
        cin >> s;
        spear.push_back(s);
    }
    for (int i = 0; i < n; i++) {
        vector<pair<int, int>> clu;
        crush(spear[i], i);
        int cnt = 1;
        
        for (int j = 0; j < r; j++) {
            for (int k = 0; k < c; k++) {
                if (map[j][k] == 'x' && d[j][k][i] == 0) {
                    vector<pair<int,int> > v = cluster(j, k, cnt,i);
                    cnt++;
                    if (v.size() != 0) {
                        clu = v;
                    }
                }
            }
        }
        
        if (clu.size() != 0) {
            int value = d[clu[0].first][clu[0].second][i];
            //cout << value << " 시발!!" << '\n';
            down(clu, i,value);
        }
        
    }
    print();
    return 0;
}

BFS문제라고했는데, 사실 BFS문제라기 보다는 시뮬레이션문제에 가깝다.

군집 구하는거만 BFS로 하는거 외에는 딱히 BFS를 한게없는문제