BOJ 2933 - 미네랄

www.acmicpc.net/problem/2933

2933번: 미네랄

 

처음에 문제 읽었을땐, 클러스터 설명부분에서 많이 헷갈렸는데,

나중에 다시보니 그냥 미네랄 묶음을 클러스터라 칭하고, 막대기 던졌을때, 땅(맨 밑바닥) 과의 간격이 생겨서

공중에 뜨게 된 경우, 밑으로 내려야 하는 그런 문제 였다. 마치 테트리스 블록 내리듯이

 

 

막대기를 던지면서, 막대기가 미네랄에 맞게되면, 해당 미네랄은 사라지고, 그 미네랄이 사라짐으로 인해서 생긴 공백을 밑으로 내려줘야한다.

 

그래서 제일 먼저, 막대기를 던지는 함수(throw_stick())를 수행한다.

막대기를 던져서 미네랄과 부딪혀서 미네랄이 사라진 경우, 공백이 생겼을 수 있기 때문에, 미네랄이 공중에 떠있는지 확인하는 함수(is_air()) 를 수행한다. 

공중에 떠있는 미네랄이 있다면, 그 미네랄을 밑으로 내리는 맵을 수정하는 작업(update_map())이 필요하다.

 

 

막대기를 던지는 함수의 경우, 창영, 상근 둘 중 어느쪽이 던지느냐에 따라서 다르게 진행한다

창영은 왼쪽에서, 상근은 오른쪽에서 던지게 한다.

던져서 미네랄이 사라졌으면 true 를 리턴해준다 (제거된 미네랄이 있으므로 공백을 확인하는 함수를 수행하기 위해 bool 값으로 리턴시킴)

 

 

공중에 미네랄이 떠있는지 아닌지 확인하는 방법은, 땅바닥과 떨어져 있느냐 아니냐이다.

이를 위해서 땅바닥 부분 (R - 1) 에 대해서 BFS 를 수행하여, BFS 를 수행하면서 만나면, 땅바닥과 연결되어 있다는 의미이므로, 연결된 부분은 방문 처리해준다

BFS 를 수행하고도, 방문 처리가 안된 부분들은 공중에 떠있는 것이다.

이 공중에 떠있는 것들을 확인하기 위한 별도의 배열 bool air[][] 과 벡터 vector<pair<int, int>> air_pos 를 만든다

벡터는 좌표, bool 배열은 공중 떠 있는지 체크하기 위한 배열이다.

 

 

공중에 떠있는 미네랄들을 모두 체크한 후, 밑으로 내리는 작업을 해준다.

이때 내리는 방식은, 땅바닥과의 거리가 얼마나 되는지 계산해주면서 내린다

계산할때 주의할게, 위에서 부터 아래로 내려서 계산하는데, 같은 클러스터 소속의 미네랄을 만날경우, 거리 계산이 아무 의미가 없으므로, 이때는 INF 값을 내보내서, 무의미한 값임을 알린다.

땅바닥과의 거리 계산을 완료했으면, 맵을 갱신해서 수정한다.

 

 

- c++

#include <bits/stdc++.h>
 
#define MAX 101
#define INF 987654321
 
using namespace std;
 
int R, C, N;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
char adj[MAX][MAX];
bool visited[MAX][MAX], air[MAX][MAX]; // 공중에 떠있는 미네랄 체크를 위한 변수 
vector<int> sticks; // 던진 막대의 높이 
vector<pair<int, int>> air_pos; // 공중에 떠있는 미네랄 좌표 체크 
 
int dist(int y, int x) {
    // 클러스터를 몇칸 내려야 하는지 파악하는 함수 
    
    int cnt = 0;
    for (int i = y + 1; i < R; ++i) {
        if (adj[i][x] == 'x') { 
            if (air[i][x]) return INF; // 같은 클러스터 소속이면 거리계산이  무의미 
            else return cnt;
        } else if (adj[i][x] == '.') { // 땅 바닥과의 거리 
            cnt++;
        }
    }
    
    return cnt;
}
 
void update_map() {
    // 공중에 떠있는 클러스터를 밑으로 내리는 함수 
    
    int height = INF - 1;
    for (int i = 0; i < air_pos.size(); ++i) {
        int y = air_pos[i].first, x = air_pos[i].second;
        
        int temp = dist(y, x);
        
        if (temp == INF) continue;
        else height = min(height, temp);
    }
    
    sort(air_pos.begin(), air_pos.end());
    
    for (int i = air_pos.size() - 1; i >= 0; --i) {
        int y = air_pos[i].first, x = air_pos[i].second;
        
        adj[y][x] = '.';
        adj[y + height][x] = 'x';
    }
}
 
bool throw_stick(int row, char ch) {
    // 스틱을 던지기 위한 함수 
    
    if (ch == 'L') {
        // 왼쪽에서 던짐 
        for (int i = 0; i < C; ++i) {
            if (adj[row][i] == 'x') {
                adj[row][i] = '.';
                return true;
            }
        }
    } else {
        // 오른쪽에서 던짐
        for (int i = C - 1; i >= 0; --i) {
            if (adj[row][i] == 'x') {
                adj[row][i] = '.';
                return true;
            }
        } 
    }
    
    return false;
} 
 
void bfs(int i, int j) {
    // 미네랄 탐색을 위한 bfs 
    queue<pair<int, int>> q;
    q.push({i, j});
    visited[i][j] = true;
    
    while(!q.empty()) {
        int y = q.front().first, x = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; ++i) {
            int ny = y + dy[i], nx = x + dx[i];
            
            if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
            
            if (adj[ny][nx] == 'x' && !visited[ny][nx]) {
                visited[ny][nx] = true;
                q.push({ny, nx});
            }
        }
    } 
}
 
bool is_air() {
    // 공중에 떠있는 미네랄 확인을 위한 함수 
    
    // 밑바닥 부터 확인 
    for (int i = 0; i < C; ++i) 
        if (adj[R - 1][i] == 'x' && !visited[R - 1][i]) 
            bfs(R - 1, i);
            
    bool temp = false;
    
    memset(air, false, sizeof(air));
    
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (adj[i][j] == 'x' && !visited[i][j]) {
                temp = true;
                air_pos.push_back({i, j});
                air[i][j] = true;
            }
        }
    }
    
    return temp;
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> R >> C;
    
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            cin >> adj[i][j];
        }
    }
    
    cin >> N;
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;
        sticks.push_back(num);
    }
    
    for (int i = 0; i < sticks.size(); ++i) {
        air_pos.clear();
        memset(visited, false, sizeof(visited));
        memset(air, false, sizeof(air));
        
        char turn; // 짝홀에 따른 순서 부여
        int height = sticks[i];
        height = R - height;
        
        if (i % 2 == 0) turn = 'L';
        else turn = 'R';
        
        if (!throw_stick(height, turn)) continue; // 던졌는데 미네랄 안나옴
        
        if (!is_air()) continue; // 공중에 떠있는 미네랄 없음
        else update_map(); // 공중에 떠있는 미네랄 있으므로 맵 수정 
    }
    
    
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            cout << adj[i][j];
        }
        cout << "\n";
    }
    
    return 0;
}