[백준] 2933번: 미네랄

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

2933번: 미네랄

나머지 예제 생략

 

문제에 예외 상황이 없어서 예제는 다 맞히고 자꾸 틀려서 스트레스 받는 문제다 ㅎㅎ

일단 기본 원리들을 정리해보면,

 

1. 막대를 던지기 (Throw_Stick())

그냥 왼쪽에서부터/오른쪽에서부터 탐색하다가 미네랄이면 부시면 됨

void Throw_Stick(int n) {
    if (n % 2 == 0) {
        // 왼쪽에서 오른쪽으로 던짐
        for (int i = 0; i < C; i++) {
            if (map[R-cmd[n]][i] == 'x') {
                map[R-cmd[n]][i] = '.'; // 부시기
                break;
            }
        }
    }
    else {
        // 오른쪽에서 왼쪽으로 던짐
        for (int i = C - 1; i >= 0; i--) {
            if (map[R-cmd[n]][i] == 'x') {
                map[R-cmd[n]][i] = '.'; // 부시기
                break;
            }
        }
    }
    //Print_Map();
}

 

2. 떠 있는 클러스터 찾기 (Find_Cluster())

• 바닥 칸들에서 BFS를 시작해서 visited 배열에 표시를 한다.
• 모든 바닥칸에 대한 BFS가 끝난 후에 만약 방문이 안된 미네랄이 있으면 그 부분이 떠있는 클러스터이다. 
• 떠 있는 클러스터의 미네랄 좌표들을 cluster라는 배열에 별도 저장한다. 
• 클러스터가 있다면 1을 리턴, 아니면 0을 리턴한다.

int Find_Cluster(void) {
    // 바닥에 있는 모든 미네랄로부터 BFS한 후, 방문 안된 것이 있으면 떠 있는 클러스터
    int flag = 0;
    memset(visited, 0, sizeof(visited));
    memset(cluster, 0, sizeof(cluster));
    ccnt = 0;
    for (int i = 0; i < C; i++) {
        if (map[R - 1][i] == 'x' && visited[R - 1][i] == 0) {
            BFS(R - 1, i);
        }
    }

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (map[i][j] == 'x' && visited[i][j] == 0) {
                flag = 1;
                cluster[ccnt].y = i, cluster[ccnt++].x = j;
            }
        }
    }
    return flag;
}

 

3. 떠 있는 클러스터 내리기 (Get_Min_Height() 와 Drop_Cluster())

• 떠 있는 클러스터가 있다면 몇 칸을 내릴지를 결정해야 한다. 이를 위해 Get_Min_Height()라는 함수를 구현했다.
• Get_Min_Height()
  • 클러스터의 모든 미네랄에 대해, 그 미네랄의 위치부터 바닥까지 쭉 아래로 내려가며 탐색한다.
  • 탐색 중 . (그냥 공기)이면 cnt를 증가, 바닥에 붙어있는 미네랄 (미네랄인데, 방문된 거) 이면 탐색 끝
  • 이렇게 구하는 cnt들 중 최솟값을 찾아 리턴한다. 

  • int Get_Min_Height(void) {
        int min = 0x7fffffff;
        for (int i = 0; i < ccnt; i++) {
            int cnt = 0;
            for (int j = cluster[i].y+1; j < R; j++) {
                if (map[j][cluster[i].x] == '.') cnt++;
                if (map[j][cluster[i].x] == 'x' && visited[j][cluster[i].x] == 1) {
                    break;
                }
            }
            if (cnt < min) min = cnt;
        }
        return min;
    }

• Drop_Cluster(int h)
  • 몇 칸 내릴지를 정했으니까, cluster 배열의 모든 좌표들의 미네랄을 그만큼 내려준다.

  • void Drop_Cluster(int h) {
        for (int i = 0; i < C; i++) {
            for (int j = R - 1; j >= 0; j--) {
                if (map[j][i] == 'x' && visited[j][i] == 0) {
                    map[j + h][i] = map[j][i];
                    map[j][i] = '.';
                }
            }
        }
        //Print_Map();
    }

 

4. 정답 출력

 

문제 상황

클러스터 모양이 다양하게 나올 수 있다는 점

밑에 있는 미네랄 덩어리 어딘가에 걸릴 수 있다. 

클러스터 속 미네랄에서 아래로 내려가면서 탐색하다가 클러스터의 미네랄을 만날 수 있다는 점. (초록색)

등등.... 매우 헷갈린다..!

그리고 클러스터가 없는 경우도 고려해야 한다.!

 

전체 코드

#include <stdio.h>
#include <string.h>
#define MAXRC 100
#define MAXN 100
#define MIN(a, b) ((a) > (b) ? (a) : (b))

int R, C, N;
char map[MAXRC + 5][MAXRC + 5];
int cmd[MAXN];
int visited[MAXRC + 5][MAXRC];

typedef struct {
    int y, x;
}ELE;

ELE cluster[MAXRC * MAXRC + 10];
int ccnt = 0;

ELE q[MAXRC * MAXRC * 10];
int wp, rp;
void enq(int y, int x) { q[wp].y = y; q[wp++].x = x; }
ELE deq(void) { return q[rp++]; }
int empty(void) { return wp == rp; }

int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };

void Get_Input(void) {
    scanf("%d %d", &R, &C);
    for (int i = 0; i < R; i++) {
        scanf("%s", &map[i]);
    }
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &cmd[i]);
    }
}

void Print_Map(void) {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            printf("%c", map[i][j]);
        }
        printf("\n");
    }
    //printf("\n");
}

void Throw_Stick(int n) {
    if (n % 2 == 0) {
        // 왼쪽에서 오른쪽으로 던짐
        for (int i = 0; i < C; i++) {
            if (map[R-cmd[n]][i] == 'x') {
                map[R-cmd[n]][i] = '.'; // 부시기
                break;
            }
        }
    }
    else {
        // 오른쪽에서 왼쪽으로 던짐
        for (int i = C - 1; i >= 0; i--) {
            if (map[R-cmd[n]][i] == 'x') {
                map[R-cmd[n]][i] = '.'; // 부시기
                break;
            }
        }
    }
    //Print_Map();
}


void BFS(int sy, int sx) {
    // 초기화
    wp = 0, rp = 0;

    enq(sy, sx);
    visited[sy][sx] = 1;
    while (!empty()) {
        ELE cur = deq();
        for (int i = 0; i < 4; i++) {
            int ny = cur.y + dy[i];
            int nx = cur.x + dx[i];
            if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
            if (map[ny][nx] == '.') continue;
            if (visited[ny][nx] == 1) continue;
            enq(ny, nx);
            visited[ny][nx] = 1;
        }
    }
}

int Find_Cluster(void) {
    // 바닥에 있는 모든 미네랄로부터 BFS한 후, 방문 안된 것이 있으면 떠 있는 클러스터
    int flag = 0;
    memset(visited, 0, sizeof(visited));
    memset(cluster, 0, sizeof(cluster));
    ccnt = 0;
    for (int i = 0; i < C; i++) {
        if (map[R - 1][i] == 'x' && visited[R - 1][i] == 0) {
            BFS(R - 1, i);
        }
    }

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (map[i][j] == 'x' && visited[i][j] == 0) {
                flag = 1;
                cluster[ccnt].y = i, cluster[ccnt++].x = j;
            }
        }
    }
    return flag;
}


int Get_Min_Height(void) {
    int min = 0x7fffffff;
    for (int i = 0; i < ccnt; i++) {
        int cnt = 0;
        for (int j = cluster[i].y+1; j < R; j++) {
            if (map[j][cluster[i].x] == '.') cnt++;
            if (map[j][cluster[i].x] == 'x' && visited[j][cluster[i].x] == 1) {
                break;
            }
        }
        if (cnt < min) min = cnt;
    }
    return min;
}

void Drop_Cluster(int h) {
    for (int i = 0; i < C; i++) {
        for (int j = R - 1; j >= 0; j--) {
            if (map[j][i] == 'x' && visited[j][i] == 0) {
                map[j + h][i] = map[j][i];
                map[j][i] = '.';
            }
        }
    }
    //Print_Map();
}

int main(void) {
    int h;
    Get_Input();
    for (int n = 0; n < N; n++) {
        Throw_Stick(n);
        if(Find_Cluster()){
            h = Get_Min_Height();
            Drop_Cluster(h);
        }
    }
    Print_Map();
    return 0;
}