백준 2933 미네랄

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

2933번: 미네랄

문제

창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.

동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.

창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.

막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.

미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다. 새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다. 떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 게속해서 떨어진다. 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.

동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100)

다음 R개 줄에는 C개의 문자가 주어지며, '.'는 빈 칸, 'x'는 미네랄을 나타낸다.

다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)

마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다. 모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다. 첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.

공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다. 클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.

출력

입력 형식과 같은 형식으로 미네랄 모양을 출력한다.

예제 입력 1 복사

5 6
......
..xx..
..x...
..xx..
.xxxx.
1
3

예제 출력 1 복사

......
......
..xx..
..xx..
.xxxx.

---

[풀이 과정]

1. 빈칸은 0, 미네랄은 1로 arr배열에 저장했다.

 

2. 문제에서 제공하는 높이는 바닥이 1인데 편의상 R - row(높이)로 바꿔주었다. 

 

3. N번 막대를 던져서 미네랄을 파괴하는데 왼쪽, 오른쪽 번갈아가면서 해당 높이의 미네랄을 파괴하기 때문에 i가 짝수일 때는 왼쪽에서부터 미네랄을 찾고, i가 홀수일 때는 오른쪽에서부터 미네랄을 찾게 구현했다.

 

4. check_cluster(): 떨어질 클러스터 찾고 이동하는 함수

1) 바닥에 붙어있는 클러스터는 떨어질 일이 없기 때문에 bfs 함수로 모두 방문처리했다.

2) 이후 바닥과 떨어져있는 클러스터(아직 방문 전인데 미네랄 있는 곳)가 있는지 한번 더 bfs 함수를 실행한다. 이때 그런 곳이 있으면 이동을 위해 0으로 바꿔준다.

3) 떨어진 클러스터가 있다면 얼마나 바닥으로 내릴 수 있는지를 찾아야 한다.

- 1칸부터 R-1칸까지 늘려가면서 cluster에 포함된 모든 값들이 다 내려갈 수 있는지 확인한다.

- cur은 i번째 cluster가 최대 몇 칸 내려갈 수 있는지를 저장한 변수이고 gap은 전체 cluster가 몇 칸 내려갈 수 있는지 저장한 변수이다. 

4) gap이 10000이라면 현재 위치에서 바닥으로 내릴 수 없다는 것이기 때문에 그대로 현재 위치에 1을 넣어주고 만약 gap이 10000이 아니라면 해당 값만큼 아래로 내려준다.

 

5. 최종 arr배열을 출력한다.

---

[소스 코드]

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int MAX = 105;

int R, C, N, arr[MAX][MAX], row;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
bool visited[MAX][MAX];
vector <pair<int, int>> cluster;

void bfs(int a, int b){
    queue <pair<int, int>> q;
    q.push({a, b});
    visited[a][b] = true;

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

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

            if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
            if(!visited[nx][ny] && arr[nx][ny] == 1){
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
}

void check_cluster(){
    cluster.clear();
    memset(visited, 0, sizeof(visited));

    for(int j=0;j<C;j++){
        if(!visited[R-1][j] && arr[R-1][j] == 1){
            bfs(R-1, j);
        }
    }

    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            if(!visited[i][j] && arr[i][j] == 1){
                cluster.push_back({i, j});
                arr[i][j] = 0;
            }
        }
    }

    if(!cluster.empty()){
        int gap = 10000;

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

            for(int k=1;k<R;k++){
                if(x + k >= R || arr[x+k][y] == 1) break;
                cur = cur < k ? k : cur;
            }
            gap = gap > cur ? cur : gap;
        }
        for (int i = 0; i < cluster.size(); i++) {
            int x = cluster[i].first;
            int y = cluster[i].second;

            if(gap != 10000) arr[x+gap][y] = 1;
            else arr[x][y] = 1;
        }
    }
}

int main(){
    scanf("%d %d", &R, &C);

    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            char c;
            scanf(" %c", &c);
            if(c == '.') arr[i][j] = 0;
            else arr[i][j] = 1;
        }
    }
    scanf("%d", &N);
    for(int i=0;i<N;i++){
        scanf("%d", &row);
        row = R - row;
        if(i % 2 == 0){
            for(int j=0;j<C;j++){
                if(arr[row][j] == 1){
                    arr[row][j] = 0;
                    break;
                }
            }
        }
        else{
            for(int j=C-1;j>=0;j--){
                if(arr[row][j] == 1){
                    arr[row][j] = 0;
                    break;
                }
            }
        }
        check_cluster();
    }
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            if(arr[i][j] == 0) printf(".");
            else printf("x");
        }
        printf("\n");
    }
    return 0;
}