21611. 마법사 상어와 블리자드

문제 링크

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

풀이

이 문제의 핵심은 선형으로 저장되지 않은 데이터를 선형으로 저장된 데이터처럼 다루는 것이다. 만약 구슬이 일반적인 배열처럼 선형으로 나열되어 있었다면 연속으로 같은 숫자 제거, 폭발해서 남은 빈칸 메꾸기는 비교적 쉽게 해낼 수 있다. 문제는 구슬이 나선형으로 나열됨으로 인해 구현에 생각할 요소가 많아졌다는 것이다.

필자는 나선형 이동을 다음과 같이 생각하고 구현하였다. 주어진 전체 배열의 중심에서 나선형으로 순회할 경우, (왼쪽, 아래쪽, 오른쪽, 위쪽)의 순서로 \(n\)만큼 이동한다. 이때, 아래쪽과 위쪽으로 이동한 뒤에는 \(n\)이 1만큼 증가한다. 위 그림은 이와 같은 생각을 옮긴 것이다.

이걸 막상 구현하자니 나선형으로 이동하는 하나의 점을 객체로 만들어야만 할 것 같았다. 그래서 아래 코드를 보면 알겠지만, 평소엔 잘 쓰지도 않는 구조체(클래스)에 연산자 오버로딩까지 사용하며 구현하였다. 일단 한번 만들어 놓으니 문제풀이는 일사천리로 진행되었다만, 간만에 안 쓰던 걸 쓰느라 애 좀 먹었다.

시간 복잡도

explosion이 얼마나 호출되느냐에 따라 전체적인 시간 복잡도가 널뛰기하기 때문에 이를 정확히 알 수는 없다. 각 함수의 시간 복잡도는 다음과 같다.

• blast(블리자드 마법 시전): \(O(s)\)
• moveMarbles(빈 칸을 메우며 구슬 이동): \(O(N^{2})\)
• explosion(같은 숫자가 4개 이상 연속된 구슬 폭발): \(O(N^{2})\)
• rearrange(구슬 숫자 재배치): \(O(N^{2})\)

소스코드

#include <iostream>
#include <vector>
using namespace std;

int N, M, d, s, len;
int arr[50][50];
int dx[] = {0, -1, 1, 0, 0};
int dy[] = {0, 0, 0, -1, 1};
int order[] = {3, 2, 4, 1};
int explodeCnt[4];
vector<int> tempVec;

// 중심으로부터 나선형으로 이동하는 점 객체
struct Point {
    int x, y;
    int idx;
    int limit;
    int cnt;
    
    Point() {
        this->x = N / 2;
        this->y = N / 2;
        this->idx = 0;
        this->limit = 1;
        this->cnt = 0;
    }
    Point(const Point& p) {
        this->x = p.x;
        this->y = p.y;
        this->idx = p.idx;
        this->limit = p.limit;
        this->cnt = p.cnt;
    }    
    Point operator++() {
        this->x += dx[order[idx]];
        this->y += dy[order[idx]];
        
        if(++cnt == limit) {
            if(idx == 1 || idx == 3) ++limit;
            idx = (idx + 1) % 4;
            cnt = 0;
        }
        
        return *this;
    }
};

// 블리자드 마법 시전 함수
void blast() {
    int x = N / 2;
    int y = N / 2;
    for(int i = 0; i < s; ++i) {
        x += dx[d];
        y += dy[d];
        arr[x][y] = 0;
    }
}

// 빈 칸을 메우며 구슬을 이동시키는 함수
void moveMarbles() {
    Point p1, p2;
    int cnt = 0;
    for(int i = 0; i < len; ++i) {
        ++p2;
        if(arr[p2.x][p2.y] == 0) continue;
        ++p1;
        ++cnt;
        arr[p1.x][p1.y] = arr[p2.x][p2.y];
    }
    
    len = cnt;
}

// 연속으로 같은 숫자의 구슬을 폭발시키는 함수
bool explosion() {
    Point p1, p2;
    int i = 0;
    bool exploded = false;
    
    while(i <= len) {
        ++p2; ++i;
        int cnt = 1;
        while(i <= len && arr[p1.x][p1.y] == arr[p2.x][p2.y]) {
            ++cnt;
            ++p2;
            ++i;
        }
        
        if(cnt >= 4) {
            exploded = true;
            while(cnt--) {
                ++explodeCnt[arr[p1.x][p1.y]];
                arr[p1.x][p1.y] = 0;
                ++p1;
            }
        }
        else p1 = p2;
    }
    
    return exploded;
}

// 폭발이 끝난 구슬들을 재배치하는 함수
void rearrange() {
    Point p1, p2;
    ++p1; ++p2;
    int i = 0;
    tempVec.clear();
    
    while(i < len) {
        ++p2; ++i;
        int cnt = 1;
        while(i < len && arr[p1.x][p1.y] == arr[p2.x][p2.y]) {
            ++cnt;
            ++p2;
            ++i;
        }
        
        tempVec.push_back(cnt);
        tempVec.push_back(arr[p1.x][p1.y]);
        p1 = p2;
    }
    
    Point p3;
    len = tempVec.size() < N * N - 1 ? tempVec.size() : N * N - 1;
    for(int i = 0; i < len; ++i) {
        ++p3;
        arr[p3.x][p3.y] = tempVec[i];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> M;
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            cin >> arr[i][j];
            if(arr[i][j] > 0) ++len;
        }
    }
    
    while(M--) {
        cin >> d >> s;
        blast();
        do {
            moveMarbles();
        } while(explosion());
        rearrange();
    }
    
    cout << explodeCnt[1] + 2 * explodeCnt[2] + 3 * explodeCnt[3];
    return 0;
}