백준 2933 / 미네랄

구현하기 꽤나 복잡한 문제.

처음엔 5개의 높이마다 왼,오 두번씩 던지는 줄 알아서 꽤나 헤맸다. (...)

알고리즘을 행동별로 나누어 계층적으로 짜면 수월하다.

1. 해당되는 높이로 막대기를 던져 x가 맞으면 부순다.

2. 맵을 확인하여 클러스터를 생성, 그 클러스터가 땅에 붙어있으면 pass, 땅이나 다른 클러스터와 떨어져 있으면 3번.

3. 분리되어 있는 클러스터를 한칸 떨어뜨린다.

4. 한칸 떨어진 클러스터가 땅에 닿았는지 혹은 다른 클러스터에 닿았는지 확인한 후, 닿지 않았다면 3번. 닿았으면 다음 막대기를 던진다. 

3번을 수행할때, 맵만 바꾸어주는 것이 아니라, 클러스터를 만들때 true로 체크했던 bool 배열(check)도 바꾸어 주어야한다.

또한 한개의 포문안에서 한칸을 지우고 그 밑에 x를 입력하는 것이 아닌,

한 칸을 지우는 포문 한개와 밑에 x를 입력하는 포문 한개, 즉 2개를 사용하는 것이 정확하다.

4번에서 자신의 클러스터와 다른 클러스터를 구별하기 위해 부울 배열(own)을 사용했다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<memory.h>
 
using namespace std;
 
bool check[101][101];
 
char map[101][101];
int thigh[101];
 
int n, m;
int thnum;
 
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
vector<pair<int, int>>cluster;
 
void clust();
 
void down() {  // 분리된 클러스터를 떨어뜨리는 함수
 
    bool ok = false;
    bool own[101][101];
 
    memset(own, false, sizeof(own));
 
    for (int i = 0; i < cluster.size(); i++) {
        int x = cluster[i].first;
        int y = cluster[i].second;
 
        if (x == n - 1) {
            ok = true;
            break;
        }
    }
 
    if (ok == false) {
        
        for (int i = 0; i < cluster.size(); i++) {
            int x = cluster[i].first;
            int y = cluster[i].second;
 
            
            map[x][y] = '.';
            check[x][y] = false;
            
        }
 
        for (int i = 0; i < cluster.size(); i++) {
            int x = cluster[i].first;
            int y = cluster[i].second;
 
 
            map[x + 1][y] = 'x';
 
            check[x + 1][y] = true;
            own[x+1][y] = true;
 
            cluster[i].first++;
 
        }
        bool on = false;
 
        for (int i = 0; i < cluster.size(); i++) {
            int x = cluster[i].first;
            int y = cluster[i].second;
 
            if (x == n - 1) {
                on = true;
            }
            if (map[x + 1][y] == 'x' && own[x+1][y] == false) {
                on = true;
            }
        }
        if (on == false) {
            down();
        }
        else {    
             return;
        }
    
    }
    return;
}
 
void make(int x, int y) {  // 클러스터를 만드는 함수
    cluster.push_back({ x,y });
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
            if (map[nx][ny] == 'x' && check[nx][ny] == false) {
                check[nx][ny] = true;
                make(nx, ny);
 
            }
        }
    }
}
void clust() {   // 클러스터를 만드는 함수와 떨어뜨리는 함수
 
    memset(check, false, sizeof(check));
 
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 'x' && check[i][j]==false) {
                cluster.clear();
                check[i][j] = true;
                make(i, j);
 
                down();
            }        
        }
    }
    return;
}
 
void go(int high, int dir) {  //막대기 던져서 부수는 함수
    high = n - high;
    
    if (dir == 1) { //왼 -> 오
        for (int i = 0; i < m; i++) {
            if (map[high][i] == 'x') {
                map[high][i] = '.';
                break;
            }
        }
 
    }
    if (dir == -1) { // 오->왼
        for (int i = m-1; i >= 0; i--) {
            if (map[high][i] == 'x') {
                map[high][i] = '.';
                break;
            }
        }
    }
 
    return;
 
}
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
    cin >> thnum;
 
    for(int i = 0; i < thnum; i++) {
        cin >> thigh[i];
    }
 
    for (int i = 0; i < thnum; i++) {
        
        if (i % 2 == 0) {
            go(thigh[i], 1);
 
        }
        else {
            go(thigh[i], -1);
 
        }
        clust();        
    }
 
 
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < m; k++) {
            cout << map[j][k];
        }
        cout << endl;
    }
    cout << endl;
 
}