[백준 / BOJ] 2933 :: 미네랄

www.acmicpc.net/problem/2933

2933번: 미네랄

문제 설명 : 

막대기를 한번은 왼쪽에서 오른쪽으로, 다른 한번은 오른쪽에서 왼쪽으로 던질 것이다.

이때 각 방향으로 탐색해서 오면서 처음 만나는 미네랄을 캘 것이다.(미네랄이 있는 곳이 0 처리됨)

 

미네랄은 클러스터(군집)이 있다. 상하좌우로 연결된 미네랄은 같인 미네랄 클러스터이다.

미네랄을 캐면서 하나의 미네랄이 없어지는데, 이 때 기존에 연결되어 있던 클러스터가 서로 분리 될 수도 있다.

그러면 그 두 클러스터 중 하나의 클러스터는 아래로 떨어지게 된다.

 

떨어지는 것을 멈추게 되는 조건은 두개 중 하나이다.

다른 클러스터를 만나거나, 바닥에 부딪히거나.

 

이렇게 모든 작업을 끝내고 최종적인 map의 모습을 출력하면 된다.

 

 

문제 해결:

우선, N번의 작업을 수행하는 것을 시뮬레이션 시켜야 한다.

 

각 작업을 했을 때 처음으로 판단해야 하는 것은, 미네랄을 캤을 때 두 클러스터가 분리되었는지 분리 되지 않았는지를 판단해야 한다. 분리 기준에는 두 개가 있다. 서로 다른 클러스터로 분리된 경우 / 공중에서 뜬 경우

이를 위해 우리는 미네랄 하나를 캐고(map에서 0처리) , 그 후 다시 군집을 만든다.

군집을 만든다는 개념은 마치 아파트단지에 번호를 붙이는 느낌이다.

이런식으로 이웃한 클러스터마다 고유의 번호를 붙여준다.

 

우리는 캔 미네랄의 위치를 0으로 만들고, 매번 다시 이 번호를 계산하여 매기면 된다.

이 번호를 매긴 후, 캐어진 미네랄 위치를 기준으로 상하좌우 클러스터 번호를 탐색한다. 상하좌우 중 클러스터 번호가 다른 경우가 있다면 이는 분리된 클러스터가 존재하는 경우이다.

 

그렇다면 공중에서 뜬 경우는? 

작업하는 위치가 1번인 경우, 1번 라인에 현재 클러스터와 번호와 일치하는 번호가 없는지 판단하면 된다. 이렇게!

 

여기까지 분리되었는지 판단하는 과정이다.

분리가 되었는지 판단하는 과정에서 우리는 꼭 떨어지는(이동이 필요한) 클러스터의 번호를 가지고 있어야 한다.

 

분리가 되었다면, 이제 클러스터를 이동시켜야 한다.

결국에는 아래 방향으로의 평행이동이다.

우리는 최소 몇칸을 평행이동 시키면 되는지를 찾아야한다.

 

그냥 완전탐색 돌리면서, 움직이려는 클러스터 번호가 몇칸 이동했을때 바닥을 만나거나, 다른 클러스터를 만나는지 판단하고, 그 모든 값들 중 최소 값을 잡으면된다.

 

최소 값을 구하고 나면 , 클러스터를 이동시켜 새로게 맵을 업데이트하고, 다음 작업을 위해 다시 클러스터 번호를 매겨준다.

 

 

말로 설명하면 좀 복잡하지만, 코드를 보고 이해해보자..

 

 

소스코드

 

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int R, C, N;
vector<int> job;
int map[101][101];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
bool visited[101][101];
 
void print() {
    for (int i = R; i >= 1; i--) {
        for (int j = 1; j <= C; j++) {
            cout << map[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl;
}
void dfs(int x, int y, int num) {
    queue<pair<int, int > > q;
    q.push({ x,y });
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx > R || nx <1 || ny > C || ny < 1) continue;
            if (map[nx][ny] != 0 && visited[nx][ny] == false) {
                map[nx][ny] = num;
                visited[nx][ny] = true;
                q.push({ nx,ny });
            }
        }
    }
}
void makeCluster() {
    for (int i = 0; i < 101; i++) {
        for (int j = 0; j < 101; j++) {
            visited[i][j] = false;
        }
    }
    int cnt = 1;//clsuter count number;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (map[i][j] != 0 && visited[i][j] == false) {//미네랄이 있는 위치
                map[i][j] = cnt;
                dfs(i, j, cnt);
                cnt++;
            }
        }
    }
}
int main() {
    cin >> R >> C;
    for (int i = R; i >= 1; i--) {
        string s;
        cin >> s;
        for (int j = 0; j < C; j++) {
            if (s[j] == '.') map[i][j + 1] = 0;
            else if (s[j] == 'x') map[i][j + 1] = -1;
        }
    }
    for (int i = 1; i <= C; i++) {
        map[0][i] = 102;
    }//바닥 설정
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        int tmp;
        cin >> tmp;
        job.push_back(tmp);
    }
    makeCluster();
 
 
    for (int cnt = 0; cnt < N; cnt++) {
        //cout << job[cnt] << " : " << endl;
        //print();
 
        bool flag = false;
        int fall_cluster;
        int now = 0;
        if (cnt % 2 == 0) { //왼쪽에서 오른쪽으로 
            for (int j = 1; j <= C; j++) {
                if (map[job[cnt]][j] != 0) {
                    now = map[job[cnt]][j];
                    map[job[cnt]][j] = 0;//미네랄 캠
                    makeCluster();
                    for (int k = 0; k < 4; k++) {
                        int nx = job[cnt] + dx[k];
                        int ny = j + dy[k];
                        if (nx > R || nx <1 || ny > C || ny < 1) continue;
                        if (map[nx][ny] != 0) {
                            if (now != map[nx][ny]) {//클러스터가 분리된 경우
                                //cout << i << " : " << "분리됨!" << endl;
                                fall_cluster = map[nx][ny];
                                flag = true;
                            }
                        }
                    }
                    break;
                }
            }
 
 
        }
        else {//오른쪽에서 왼쪽으로 
            for (int j = C; j >= 1; j--) {
                if (map[job[cnt]][j] != 0) {
                    now = map[job[cnt]][j];
                    map[job[cnt]][j] = 0;//미네랄 캠
                    makeCluster();
                    for (int k = 0; k < 4; k++) {
                        int nx = job[cnt] + dx[k];
                        int ny = j + dy[k];
                        if (nx > R || nx <1 || ny > C || ny < 1) continue;
                        if (map[nx][ny] != 0) {
                            if (now != map[nx][ny]) {//클러스터가 분리된 경우
                                flag = true;
                                fall_cluster = map[nx][ny];
 
                                //cout << i<<" : " <<"분리됨!" << endl;
                            }
                        }
                    }
                    break;
                }
            }
        }
 
        if (!flag && job[cnt] == 1) {//공중에서 떴는지 확인
            bool tmp_flag = false;
            for (int j = 1; j <= C; j++) {
                if (map[1][j] == now) {
                    tmp_flag = true;
                    break;
                }
            }
            if (!tmp_flag) {
                flag = true;
                fall_cluster = now;
            }
        }
 
        if (flag) {//클러스터가 분리된 경우 
            //cout<< "분리됨" << endl;
            int bottom;
            int move = 101;//아래로 평행이동 해야하는 칸의 수 
            int tmp = 0;
            for (int i = R; i >= 1; i--) {
                for (int j = 1; j <= C; j++) {
                    if (map[i][j] == fall_cluster) {
                        bottom = i;
                        break;
                    }
                }
            }
            //cout << "bottom : " << bottom << endl;
            for (int i = 1; i <=R ; i++) {
                for (int j = 1; j <= C; j++) {
                    if (map[i][j] == fall_cluster) {
                        int tmp = 1;
                        while (i - tmp >= 0) {
                            if (map[i - tmp][j] != 0 && map[i-tmp][j] != fall_cluster) {
                                move = min(tmp, move);
                                break;
                            }
                            else tmp++;
                        }
                    }
                }
            }
            
            //cout << "움직여야 하는 칸의 수 : " << move<< endl;
            move--;
            for (int i = 1; i <= R; i++) {
                for (int j = 1; j <= C; j++) {
                    if (map[i][j] == fall_cluster) {
                        if (map[i - move][j] == 0) {
                            map[i - move][j] = fall_cluster;
                            map[i][j] = 0;
                        }
                    }
                }
            }
            makeCluster();
        }
        
    }
    for (int i = R; i >= 1; i--) {
        for (int j = 1; j <= C; j++) {
            if (map[i][j] == 0)
                cout << ".";
            else
                cout << "x";
        }
        cout << endl;
    }
 
 
}