백준 21611번: 마법사 상어와 블리자드 - C++

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

21611번: 마법사 상어와 블리자드

1.문제설명

해당 문제에서 거쳐야하는 과정을 크게 4가지로 분리할 수 있다.

 

1. 블리자드해서 구슬을 삭제한다.

2. 구슬의 빈자리를 메꾸도록 모든 구슬을 앞으로 이동시킨다.

3. 구슬폭발 : 이동후 같은 구슬이 4개 이상 모여있는 구슬들을 삭제한다. (삭제후 2번과 동일하게 앞으로 이동)

4. 구슬변화 : 남아있는 구슬을 확인하면서, 연속된 구슬의 개수와 해당 구슬의 숫자로 구슬을 변화시킨다.

 

 

이 문제를 풀기 위한 배열과 연결리스트 중 어떤 자료구조를 선택할 지 고민했는데,

구슬폭발로 인해 원소를 자주 삭제해야하니까 연결리스트가 시간복잡도 상 유리하지 않을까 생각했다.

 

그런데 좀 더 생각해보니 구슬이 폭발한다고 원소를 바로 바로 삭제해서 푸는게 아니라

폭발하기 전 배열에서 폭발할 구슬들을 확인한 후 제외하는 방식으로 풀어야하기 때문에

인덱스 접근을 해야할 일이 많아서 배열로 푸는 것으로 결정했다.

 

 

의문이 들었던 것 중 하나는

4. 구슬변화 후 다시 구슬폭발이 일어나는 경우가 있지 않을 까 의심했는데,

깊이 생각해보니 구슬폭발이 모두 끝난 후에는 구슬 변화로 인해 연속적인 구슬 4개가 생길 수 없다.

예를 들어서 2가 2개 있는 경우, 또 2가 2개있는 경우 이러면 2222가 되니까 또 폭발할 수 있지 않을 까 생각했는데

애초에 구슬폭발이 모두 끝난 경우에는 2가 2개, 2가 2개 이런 경우가 나타날 수 없다.

다른 경우도 마찬가지이다.

 

 

문제에서 2차원 배열 형식으로 그림을 제공했지만

이를 1차원 배열로 전환한 후 문제를 해결해야한다.

반복문을 통해서 2차원배열의 1번부터 N*N-1번까지 돌 수 있다.

 

블리자드를 구현할 때는 1차원 배열내에서 가능한데,

계차수열을 이용해서 1차원 배열에서 반복문을 돌면서 배열의 원소를 지워나가면 해결할 수 있다.

 

2.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

int N, M, originArr[51][51], marbles[2501], ans[4];

void originToMarbles() {
    int x = (N + 1) / 2;
    int y = x;

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

    int curDir = 0;
    int moveCnt = 1;
    int turnDirCnt = 0;

    for (int i = 0; i < N * N; i++) {
        marbles[i] = originArr[x][y];
        turnDirCnt++;

        x += dx[curDir];
        y += dy[curDir];

        if (turnDirCnt == moveCnt) {
            if (curDir == 1 || curDir == 3) moveCnt++;
            curDir = (curDir + 1) % 4;
            turnDirCnt = 0;
        }
    }
}

void blizzard(int d, int s) {
    int firstNum[5] = {0, 7, 3, 1, 5};
    int firstStep[5] = {0, 15, 11, 9, 13};

    int num = firstNum[d];
    int step = firstStep[d];
    for (int i = 1; i <= s; i++) {
        marbles[num] = 0;
        num += step;
        step += 8;
    }
}

void marbleMove() {
    int tmp[2501];
    memset(tmp, 0, sizeof(tmp));
    int tmpIdx = 1;

    for (int i = 1; i < N * N; i++) {
        if (marbles[i] == 0) continue;
        tmp[tmpIdx++] = marbles[i];
    }
    swap(marbles, tmp);
}

bool marbleExplode() {
    bool flag = false;
    int sameFirst = 1;
    int sameCnt = 1;
    for (int i = 2; i <= N * N; i++) {
        if (marbles[i] != 0 && marbles[i] == marbles[i - 1]) {
            sameCnt++;
        } else {
            if (sameCnt >= 4) {
                ans[marbles[i-1]] += i - sameFirst;
                for (int j = sameFirst; j <= i - 1; j++) {
                    marbles[j] = 0;
                }
                flag = true;
            }
            sameFirst = i;
            sameCnt = 1;
        }
    }
    return flag;
}

void marbleChange() {
    int tmp[2501];
    memset(tmp, 0 ,sizeof(tmp));
    int tmpIdx = 1;

    int sameCnt = 1;
    for(int i=2; i<=N*N; i++){
        if(marbles[i]==marbles[i-1]){
            sameCnt++;
        }
        else{
            tmp[tmpIdx++] = sameCnt;
            if(tmpIdx == N*N) break;
            tmp[tmpIdx++] = marbles[i-1];
            if(tmpIdx == N*N) break;
            sameCnt = 1;
        }
    }
    swap(tmp, marbles);
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> originArr[i][j];
        }
    }

    originToMarbles();


    for (int i = 1; i <= M; i++) {
        int d, s;
        cin >> d >> s;
        blizzard(d, s);
        marbleMove();
        while (marbleExplode()) {
            marbleMove();
        }
        marbleChange();
    }
    
    cout << ans[1] + 2 * ans[2] + 3 * ans[3] << '\n';
    return 0;
}