#2933 미네랄

문제 링크 : https://www.acmicpc.net/problem/2933

2933번: 미네랄

 

문제를 이해하는 것만 해도 시간이 오래걸렸다.

 

뭔가 이런 류의 문제들은 방법이 생각나더라도 너무 노가다의 향이 진해 다른 더 좋은 방법은 없을까 계속해서 고민하게 된다.

 

로직을 짜고 코딩을 하는데 잔실수들이 많기도 하고 미처 고려해주지 않은 오류들이 자꾸 발생한다.

 

익숙해질만큼의 시간이 필요해 보인다.

 

 

 

양 옆으로 막대기를 던져 걸리는 미네랄을 지우는 것은 쉽다.

 

하지만 그 후 떨어질 수 있는 cluster를 아래의 cluster에 연결하는 방법이 문제이다.

 

 

나 같은 경우에는 동굴 밑에 한 층을 더 만든 뒤 그 중 한 칸 (왼쪽 아래)에서 출발하여 이어진 미네랄들을 체크해주었다.

 

그런 다음 맵 전체를 돌며 체크되지 않은 미네랄을 고른 뒤 (떨어질 수 있는 cluster는 최대 한 개이기 때문에 동굴의 바닥과 연결되지 않은 미네랄들은 한 cluster로 다 연결되어 있을것이기 때문) 이 미네랄이 속한 cluster의 각각 요소들을 파악하고 떨어질 수 있는 최소 높이를 구해주었다.

 

그런 다음 계산된 최소 높이만큼 cluster를 떨어뜨린다.

 

#include <bits/stdc++.h>

using namespace std;

int r, c;
int dir_x[4] = {0, 1, 0, -1};
int dir_y[4] = {-1, 0, 1, 0};
char state[101][101];

bool is_out(int x, int y) { return x < 0 || y < 0 || y > r || x == c; }

void break_mineral(int dir, int height) {
    int x = (dir == 1) ? 0 : c - 1;

    while ((0 <= x) && (x < c)) {
        if (state[height][x] == 'x') {
            state[height][x] = '.';
            break;
        }
        x += dir_x[dir];
    }

    queue<pair<int, int> > q;
    q.push({0, r});
    bool is_visited[101][101] = {
        0,
    };
    is_visited[r][0] = true;

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        int cur_x = cur.first;
        int cur_y = cur.second;

        for (int i = 0; i < 4; i++) {
            int new_y = cur_y + dir_y[i];
            int new_x = cur_x + dir_x[i];

            if (is_out(new_x, new_y) || state[new_y][new_x] == '.') {
                continue;
            }

            if (is_visited[new_y][new_x]) {
                continue;
            }

            is_visited[new_y][new_x] = true;
            q.push({new_x, new_y});
        }
    }

    bool stop_flg = false;
    for (int y = r - 1; y > 0; y--) {
        for (int x = 0; x < c; x++) {
            if (state[y][x] == 'x' && !is_visited[y][x]) {
                vector<pair<int, int> > cluster;
                q.push({x, y});
                state[y][x] = '.';
                int min_h = 1000;
                while (!q.empty()) {
                    pair<int, int> cur = q.front();
                    q.pop();

                    int cur_x = cur.first, cur_y = cur.second;
                    cluster.push_back({cur_x, cur_y});

                    for (int i = 0; i < 4; i++) {
                        int new_x = cur_x + dir_x[i];
                        int new_y = cur_y + dir_y[i];

                        if (is_out(new_x, new_y) ||
                            state[new_y][new_x] == '.') {
                            continue;
                        }
                        state[new_y][new_x] = '.';
                        q.push({new_x, new_y});
                    }

                    int above_y = cur_y + 1;
                    while (above_y < r && !is_visited[above_y][cur_x]) {
                        above_y++;
                    }
                    min_h = min(min_h, above_y - cur_y - 1);
                }

                for (auto xy : cluster) {
                    state[xy.second + min_h][xy.first] = 'x';
                }
                stop_flg = true;
                break;
            }
        }
        if (stop_flg) {
            break;
        }
    }
}

int main() {
    scanf("%d %d", &r, &c);

    for (int y = 0; y < r; y++) {
        for (int x = 0; x < c; x++) {
            scanf(" %c ", &state[y][x]);
        }
    }

    for (int x = 0; x < c; x++) {
        state[r][x] = 'x';
    }

    int n;
    scanf("%d", &n);

    int tmp;
    int dir = 1;
    while (n--) {
        scanf("%d", &tmp);
        break_mineral(dir, r - tmp);
        dir = (dir + 2) % 4;
    }

    for (int y = 0; y < r; y++) {
        for (int x = 0; x < c; x++) {
            printf("%c", state[y][x]);
        }
        printf("\n");
    }
}

 

백준 사이트에 올려 진 단기간 성장 문제집을 위에서부터 따라가려 하는데 #3197 백조의 호수는 로직은 다 생각해놓고 계속 미루고 있다.

 

언제 풀지..