[백준] 2933번 미네랄

2933번 미네랄

문제

---

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

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

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

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

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

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

입력

---

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

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

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

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

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

출력

---

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

---

풀이)

문제 설명 그대로 구현만 하면 되는 문제다.

BFS를 이용했다.

푼 과정은 이러하다.

1. char map[][]에 동굴 상태를 저장한다.

2. 막대를 던질 높이(height)를 입력받고, 값을 수정해준다.

    height = R - height + 1

   (입력받은 높이는 아래서부터 ↑ 1 ~ R인데, 배열은 위에서부터 ↓ 1 ~ R이므로)

   

   ex) R = 8일때, 입력받은 높이가 6일 경우 실제 배열상의 행 높이는 8 - 6 + 1 = 3 이다.

3. 몇 번째에 막대를 던진지 보고 오른쪽에서 왼쪽으로 던진 건지 왼쪽에서 오른쪽으로 던진 건지 확인한다.

   막대를 던진 방향이 확인되면, 방향대로 map을 탐색해 미네랄을 만날경우 파괴한다.

4. 바닥에 붙어 있는 클러스터들에 대해 BFS를 통해 각자 번호를 붙여준다. 

    (바닥에 붙어있는 클러스터 = 클러스터 각 열의 맨 아래 부분이 R행에 있는 클러스터)

5. 공중에 떠 있는 클러스터가 있는지 탐색하며, 발견할 경우 BFS를 통해 그 클러스터에 번호를 붙여준다.

    (map[][] == 'x' 인데, 바닥에 붙어 있는 클러스터에 포함되지 않은 미네랄일 경우 공중의 클러스터에 속한 미네랄)

   5.1 번호를 붙여주며, 클러스터 영역(미네랄 위치들)을 vector<pair<int,int>>에 삽입해준다.

  모두 삽입되었을 때 vector를 정렬해준다.

        정렬은 오름차순으로 정렬해준다.

   (클러스터의 각 열의 맨 아래 부분부터 확인해주기 위해서이다)

   (오름차순 정렬을 위해 greater<int>()사용)

   5.2 정렬된 위치들을 처음에서부터 하나씩 꺼내보며, 그 위치에서 몇 칸을 아래로 내려야 

        다른 클러스터를 만나거나 바닥에 닿는지 칸 수를 구한다.

   5.3 구한 칸 수대로 클러스터 영역 내 위치들 즉, vector에 저장된 위치들을 아래로 내려준다.

다시 2번으로 돌아간다.

코드)

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
 
int R, C, N;
char map[102][102];
int visited[102][102];
int dy[4] = { 0,0,-1,1 };
int dx[4] = { -1,1,0,0 };
void broke(int r, int dir) {
    
    if (dir % 2 == 0) { //오른쪽 ->왼쪽
        for (int i = C; i >= 1; i--) {
            if (map[r][i] == 'x') {//미네랄을 만남
                map[r][i] = '.'; //미네랄 파괴
                break;
            }
        }
 
    }
    else {//왼쪽 ->오른쪽
        for (int i = 1; i <= C; i++) {
            if (map[r][i] == 'x') {
                map[r][i] = '.'; 
                break;
            }
        }
    }
 
    //바닥에 붙어있는 클러스터를 제외하고 공중에 떠있으면 아래로 내림
    queue <pair<int, int>> qu;
    int y, x, ny, nx;
    int num = 1;//클러스터 번호
 
    for (int i = 1; i <= C; i++) { // 바닥에 붙은 클러스터들 확인
        if (map[R][i] == 'x' && visited[R][i] == 0) {
            qu.push({ R,i });
            visited[R][i] = num;
            while (!qu.empty())
            {
                y = qu.front().first;
                x = qu.front().second;
                qu.pop();
                for (int i = 0; i < 4; i++) {
                    ny = y + dy[i];
                    nx = x + dx[i];
                    if (ny<1 || ny > R || nx<1 || nx>C || visited[ny][nx] > 0) continue;
                    if (map[ny][nx] == 'x') {
                        visited[ny][nx] = num;
                        qu.push({ ny,nx });
                    }
                }
            }
            num++;
        }
 
    }
    
    for (int i = R; i >= 1; i--) {//공중에 떠있는 클러스터들 확인
        for (int j = 1; j <= C; j++) {
            if (map[i][j] == 'x' && visited[i][j] == 0) {
                qu.push({ i,j });
                vector <pair<int, int>> down;    
                down.push_back({ i,j });
                visited[i][j] = num;
                while (!qu.empty())
                {
                    y = qu.front().first;
                    x = qu.front().second;
                    qu.pop();
                    for (int i = 0; i < 4; i++) {
                        ny = y + dy[i];
                        nx = x + dx[i];
                        if (ny<1 || ny > R || nx<1 || nx>C || visited[ny][nx] > 0) continue;
                        if (map[ny][nx] == 'x') {
                            visited[ny][nx] = num;
                            qu.push({ ny,nx });
                            down.push_back({ ny,nx });
                        }
 
                    }
                }
 
                //공중에 뜬 클러스터의 맨 아래있는 미네랄이 
                //다른 클러스터에 닿을 때까지 or 바닥에 닿을 때까지 
                sort(down.begin(), down.end(),greater<pair<int,int>>());//가장 아래쪽부터 확인하기 위해 sort
                int cnt = 1; // 몇 칸을 아래로 내려야 하는지 칸 수
                bool check = false;
                while (true)
                {
                    
                    for (int i = 0; i < down.size(); i++) {
                        ny = down[i].first + cnt;
                        nx = down[i].second;
                        if ((map[ny][nx] == 'x' && visited[ny][nx] != num) || ny > R) {
                            check = true;
                            break;
                        }
                    }
                    if (check) break;
                    cnt++;
                }
                cnt--;
                //내려야할 칸 대로 클러스터 영역들 내려주기
                for (int i = 0; i < down.size(); i++) {
                    map[down[i].first][down[i].second] = '.';
                    visited[down[i].first][down[i].second] = 0;
                    map[down[i].first + cnt][down[i].second] = 'x';
                    visited[down[i].first + cnt][down[i].second] = num;
                }
 
                num++;
            }
        }
    }
 
    //다음 계산을 위해 초기화
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            visited[i][j] = 0;
            //printf("%c", map[i][j]);
        }
        //printf("\n");
    }
    //printf("---------------------\n");
}
int main() {
 
    scanf("%d %d", &R, &C);
    getchar();
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            scanf("%c",&map[i][j]);
        }
        getchar();
    }
    scanf("%d", &N);
    int height;
    for (int i = 1; i <= N; i++) {
        scanf("%d", &height);
        height = R - height + 1;
        broke(height, i);
    }
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            printf("%c", map[i][j]);
        }
        printf("\n");
    }
    return 0;
}