[백준] 2933: 미네랄

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

2933번: 미네랄

 

복잡한 DFS 문제를 풀고 싶어서 도전했다가 아주 큰 코 다쳤다.

사실 DFS부분은 큰 무리 없이 처리하였으나 시뮬레이션 과정에서, 마치 테트리스 같이 이동하는 게 정말 쉽지 않았다.

 

이 문제는 크게 

1) 창영이와 상근이가 번갈아가며 막대기 던지기 ➡️ 시뮬레이션

2) 분리된 클러스터 존재 유무 파악 ➡️ DFS(바운드 주의)

3) 존재할 시에는 중력의 힘으로 내리기 ➡️ 시뮬레이션(y좌표를 기준으로 내림차순 정렬 후 일정한 간격으로 내리기)

 

로 나눌 수 있다.

 

1,2은 어렵지 않으나 3이 매우 어려웠다.

우선 문제에 주어진 입력에서 반드시 허공을 날아다니는 클러스터는 최대 1개라는 점을 간과하면 안된다.

그리고 그게 바닥에 붙어있는 클러스터가 1개라는 것과는 무관하다. 즉 바닥에 붙어있는 클러스터는 여러 개가 가능하다.

 

그리고 점을 한 방향으로 이동할 때는 반드시 해당 방향에서부터 차근차근 옮겨야 한다.

그렇지 않으면 내용물이 뒤엉킨다.

☎️ 주의

✔︎ 인덱스명 중복을 주의하자

✔︎ 기능이 많은 경우 함수 분리를 통해 가독성을 향상하자

 

✔︎ 구현해야할 프로세스를 명확하게 세운 뒤 코드를 작성하자

 

✔︎ 엣지 케이스를 확인해보자

 

 

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
int dr[] = {0, 0, -1, 1};
int dc[] = {1, -1, 0, 0};
vector<string> arr;
int r, c;

bool inside(int x, int y) {
    return x >= 0 && x < r && y >= 0 && y < c;
}
void dfs(int x, int y, vector<vector<int>> &visited) {
    visited[x][y] = 1;
    for(int k = 0;k < 4;k++) {
        int nr = x + dr[k];
        int nc = y + dc[k];

        // 탐색 시에는 항상 인덱스 바운드 주의
        if(inside(nr,nc)) {
            if(arr[nr][nc] == 'x' && !visited[nr][nc]) {
                dfs(nr, nc, visited);
            }
        }
    }
}

void print() {
    for(int i = 0;i < r;i++) {
        for(int j = 0;j < c;j++) {
            cout << arr[i][j];
        }
        cout << endl;
    }
}


void destroy(int turn, int num) {
    int x = r - num;
    if(turn % 2 == 0) {
        for(int j = 0;j < c;j++) {
            if(arr[x][j] == 'x') {
                arr[x][j] = '.';
                break;
            }
        }
    }
    else {
        for(int j = c - 1;j >= 0;j--) {
            if(arr[x][j] == 'x') {
                arr[x][j] = '.';
                break;
            }
        }
    }
}

vector<pair<int, int>> separate(vector<vector<int>> &visited) {
    vector<pair<int, int>> blocks;

    // 바닥과 연결된 그룹만 확인
    for(int j = 0;j < c;j++){
        if(arr[r - 1][j] == 'x') {
            dfs(r - 1, j, visited);
        }
    }

    for(int i = 0;i < r;i++){
        for(int j = 0;j < c;j++) {
            // 방문되지 않은 미네랄 클러스터에 저장하고 2로 표시
            if(arr[i][j] == 'x' && !visited[i][j]) {
                visited[i][j] = 2;
                blocks.push_back({i, j});
            }
        }
    }

    // 최하단의 미네랄부터 움직이기 위함
    // 아래부터 차근차근 내려야 함
    sort(blocks.begin(), blocks.end(), [](pair<int,int> a, pair<int,int> b) {
        return a.first > b.first;
    });

    return blocks;
}

void gravity(vector<pair<int, int>> &blocks, vector<vector<int>> &visited) {
    int block_r, block_c, block_nr, h, min_h = c;
    // 무조건 가장 r값이 크다고 먼저 땅이나 다른 클러스터에 닿는 것이 아님
    for(auto b : blocks) {
        tie(block_r, block_c) = b;
        block_nr = block_r + 1;
        // r에 아직 도착 안 하고 x 만날 때까지
        while(block_nr < r && arr[block_nr][block_c] != 'x') {
            block_nr++;
        }
        // 지금 같이 내려야하는 클러스터에 속한 x의 경우에는 패스
        if(visited[block_nr][block_c] == 2) continue;
        h = block_nr - block_r - 1;
        min_h = min(h, min_h);
    }
    for(int i = 0;i < blocks.size();i++) {
        tie(block_r, block_c) = blocks[i];
        arr[block_r + min_h][block_c] = 'x';
        arr[block_r][block_c] = '.';
    }
}
int main() {
    int n;
    vector<int> cmd;

    cin >> r >> c;
    for(int i = 0;i < r;i++) {
        string str;
        cin >> str;
        arr.push_back(str);
    }
    cin >> n;

    // i가 짝수면 창영, 홀수는 상근
    for(int turn = 0;turn < n;turn++) {
        int num;
        vector<vector<int>> visited(101, vector<int> (101 ,0));
        cin >> num;

        destroy(turn, num);
        vector<pair<int, int>> blocks = separate(visited);

        if(!blocks.empty()) {
            gravity(blocks, visited);
        }
    }

    print();
    return 0;
}