[백준 2933] 미네랄

[백준 2933] 미네랄

문제 링크

#include "header.h"
using namespace std;
int R, C, N;
char map_[101][101];
vector<int> order;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int visit[101][101];
int cluster_visit[101][101];
void input() {
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> map_[i][j];
        }
    }

    cin >> N;
    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        order.push_back(n);
    }
}
void print() {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cout << map_[i][j];
        }
        cout << endl;
    }
}
int throw_sphere(int order, int isLeft) {
    if (isLeft) {
        for (int i = 0; i < C; i++) {
            if (map_[R - order][i] == 'x') {
                map_[R - order][i] = '.';
                return 1;
            }
        }
    } else {
        for (int i = C - 1; i >= 0; i--) {
            if (map_[R - order][i] == 'x') {
                map_[R - order][i] = '.';
                return 1;
            }
        }
    }

    return 0;
}
void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    visit[x][y] = 1;
    while (!q.empty()) {
        int top_x = q.front().first;
        int top_y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = top_x + dx[i];
            int ny = top_y + dy[i];

            if (visit[nx][ny] || map_[nx][ny] == '.' || nx < 0 || ny < 0 || nx >= R || ny >= C) continue;

            q.push({nx, ny});
            visit[nx][ny] = 1;
        }
    }
}

void check() {
    vector<pair<int, int>> cluster;
    for (int i = 0; i < C; i++) {
        if (!visit[R - 1][i] && map_[R - 1][i] == 'x') {
            bfs(R - 1, i);
        }
    }

    for (int i = 0; i < R; i++) {
        for (int a = 0; a < C; a++) {
            if (!visit[i][a] && map_[i][a] == 'x') {
                cluster.push_back({i, a});
            }
        }
    }

    //down cluster
    if (!cluster.empty()) {
        int flag = 1;
        int down = 1;
        while (flag) {
            for (int i = 0; i < cluster.size(); i++) {
                int x = cluster[i].first + down;
                int y = cluster[i].second;

                if (visit[x][y] || x >= R) {
                    flag = 0;
                    break;
                }
            }

            if (!flag) break;
            down++;
        }

        for (int i = 0; i < cluster.size(); i++) {
            int x = cluster[i].first;
            int y = cluster[i].second;

            cluster_visit[x + down - 1][y] = 1;
            map_[x + down - 1][y] = 'x';
            if (!cluster_visit[x][y]) map_[x][y] = '.';
        }

        memset(cluster_visit, 0, sizeof(cluster_visit));
    }
}

void solve() {
    int left = 1;
    for (int i = 0; i < N; i++) {  //창을 던진다
        if (left) {
            if (throw_sphere(order[i], left)) check();
            left = 0;
        } else {
            if (throw_sphere(order[i], left)) check();
            left = 1;
        }
        memset(visit, 0, sizeof(visit));
    }
}
int main() {
    input();
    solve();
    print();

    return 0;
}

• bfs, 시뮬레이션 문제
• 창을 던진 후, 미네랄을 부셨다면 check()함수로 떨어진 클러스터가 있는지 확인한다.
• 땅에서부터 시작해 bfs로 방문 처리를 해 준다.
• 모든 맵을 돌면서 빙산인데도 방문 처리가 되지 않은 곳이 있다면 -> 그곳이 클러스터이다.
• 클러스터들을 벡터에 넣어주고, 내려주는 작업을 한다.
• 카카오 프렌즈 열쇠 부분이 생각 나서 비슷한 방식으로 접근 했다.
• 클러스터들을 한칸 씩 내려가면서, 만약 다른 빙산이 있다면 (visit[x][y]가 존재하면) 최대한 내려간 것이므로 break를 해 준다.
• 내려 줄 때, 기존의 빙산과 겹칠 수도 있으니 클러스터 방문 배열로 겹치지 않도록 체크 해 준다.