Baekjoon 18500번 미네랄 2

문제

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

걸린 시간

03 : 13 : 55

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int r, c;
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, -1, 1};
int visited[100][100];
vector<vector<int>> cave; // '.' : 0, 'x' : 1

int throwBar(int direction, int y){
    if(direction == 0){ // left
        for(int i = 0; i < c; i++)
            if(cave[y][i] == 1)
                return i;
    }
    else{ // right
        for(int i = c-1; i >= 0; i--)
            if(cave[y][i] == 1)
                return i;
    }
    return -1;
}

void dropCluster(int y, int x){
    cave[y][x] = 0;
    for(int i = 0; i < 4; i++){
        if(0 > y+dy[i] || r <= y+dy[i] || 0 > x+dx[i] || c <= x+dx[i]) continue;
        if(cave[y+dy[i]][x+dx[i]] == 0) continue;
        memset(visited, 0, sizeof(visited));
        vector<pair<int, int>> cluster;
        queue<pair<int, int>> q;
        cluster.push_back(make_pair(y+dy[i], x+dx[i]));
        q.push(make_pair(y+dy[i], x+dx[i]));
        visited[y+dy[i]][x+dx[i]] = 1;
        while(!q.empty()){
            int cy = q.front().first;
            int cx = q.front().second;
            q.pop();
            for(int j = 0; j < 4; j++){
                int ny = cy+dy[j];
                int nx = cx+dx[j];
                if(0 <= ny && ny < r && 0 <= nx && nx < c){
                    // find cluster set
                    if(!visited[ny][nx] && cave[ny][nx] == 1){
                        cluster.push_back(make_pair(ny, nx));
                        q.push(make_pair(ny, nx));
                        visited[ny][nx] = 1;
                    }
                }
            }
        }
        // difference mineral to bottom or other mineral
        int diff = INF;
        for(int j = 0; j < cluster.size(); j++){
            int cy = cluster[j].first;
            int cx = cluster[j].second;
            int tmp = 0;
            bool loaf = false;
            if(cy == r-1) diff = 0;
            for(int k = cy+1; k < r; k++){
                if(visited[k][cx]){
                    loaf = true;
                    break;
                }
                if(cave[k][cx] == 0) tmp++;
                else if(cave[k][cx] == 1) break;
            }
            if(loaf) continue;
            diff = min(diff, tmp);
        }
        // drop cluster set
        if(diff == 0) continue;
        for(int j = 0; j < cluster.size(); j++){
            int cy = cluster[j].first;
            int cx = cluster[j].second;
            cave[cy][cx] = 0;
        }
        for(int j = 0; j < cluster.size(); j++){
            int cy = cluster[j].first;
            int cx = cluster[j].second;
            cave[cy+diff][cx] = 1;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> r >> c;
    cave.resize(r, vector<int>(c, 0));
    char tmp;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin >> tmp;
            if(tmp == 'x') cave[i][j] = 1;
        }
    }
    int n, h;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> h;
        int y = r-h;
        int x = throwBar(i%2, y);
        if(x == -1) continue;
        dropCluster(y, x);
    }
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++)
            if(cave[i][j] == 0) cout << '.';
            else cout << 'x';
        cout << "\n";
    }
    return 0;
}

구현에 시간이 너무 오래걸린다. if 문을 중괄호를 생략하여 중첩해서 사용할 경우 else 문 사용 시 유의해야한다.