[백준] 21611번 : 마법사 상어와 블리자드(C++, 1차원 배열만 사용하는 풀이)

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

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

소요 시간

골드 2 기준으로 2시간이 소요되었습니다 ㅠㅠ

확실히 골드 1 치고는 어렵긴 했지만 이렇게 오래 걸려서야... 걱정이 크네요...

 

구상

보자마자 아... 너무 귀찮아서... 배열을 동글동글 회오리 모양으로 접근해야 하기 때문에, 차라리 이 회오리를 펼쳐서 칸 번호 순서로 나열된 1차원 배열로 표현하자는 생각이 들었습니다. 이렇게 해도 되고, 1차원 2차원 배열 둘 다 사용하면서 서로의 좌표를 map으로 대응시켜 찾아봐도 됩니다. 저는 1차원 배열만 사용했을 때 파괴된 구슬의 빈 칸을 채우는 구현이 더 간단해 질 것 같았고, 굳이 2차원 배열이 필요한 이유를 찾을 수 없어서 1차원 배열만 사용했습니다. 어떤 방법을 택하시든 칸 번호로 접근하기 편해야 합니다.

 

[1차원 배열만 사용할 때 편한 점]

- 빈 칸을 채우는 구현이 편하다(vector erase, remove함수로 간편하게 구현 가능)

- 연속하는 구슬을 확인하기 편하다

[1차원 배열만 사용할 때 불편한 점]

- d방향으로 s내의 칸을 찾기 불편하다. (마법이 시전되는 칸을 찾기 불편하다.)

 

아마도 2차원 1차원 둘 다 사용하신 분들은 2차원이 없으면 마법이 시전되는 칸을 찾기 어렵다고 생각하신 것 같습니다. 저도 이 부분 때문에 구상 시간을 좀 썼고, 결론적으로 마법이 시전되는 칸 번호의 규칙성을 찾아서 1차원 배열만 사용하면서 마법이 시전되는 칸의 칸번호를 찾을 수 있었습니다.

 

칸 번호 규칙성(중요)

왼쪽 : 1, 10, 27, 52

아래 : 3, 14, 33, 60

오른쪽 : 5, 18, 39, 68

위쪽 : 7, 22, 45, 76

 

보이시나요?! 증가량만 적어 보면

왼쪽 : 1, 9, 17, 25

아래 : 3, 11, 19, 27

오른쪽 : 5, 13, 21, 29

위쪽 : 7, 15, 23, 31

 

즉, 증가량이 8씩 증가하는 계차수열입니다.(아~ 계차수열이라는 말이 너무 오랜만이네용 ㅎㅎㅎ)

이런 일이 일어나는 이유는 당연하게도, 마법이 시전되는 다음 칸을 찾기 위해서는 한바퀴에 해당하는 칸의 갯수를 더해줘야 하는데, 회오리의 바깥쪽으로 갈수록 한 바퀴라는 것이 8씩 증가하기 때문입니다.

아무튼 초기값만 방향에 따라 1, 3, 5, 7로 설정해 주고(변환배열 사용하면 편합니다!) s개의 계차수열 항을 찾아주면 그 항들이 바로 마법이 시전되는 칸의 번호입니다.

 

위 규칙성을 반영하여 마법 시전부를 구현하고 나면, 사실 구슬을 폭파하는 것이나 변화시키는 것은 쉽습니다.

*** 주의사항 : 구현 시에 0을 맨 뒤 빈칸으로 생각하시고, 0을 0번 구슬로 카운트하지 않도록 조심하셔야 합니당

 

 

코드

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

int diToNum[5] = {0, 7, 3, 1, 5};
int answer = 0;

void do_magic(vector<int>& board, int N, int si, int di) {
    int prev = 0; int now = diToNum[di];
    for(int j=0; j<si; j++) {
        board[now] = -1;
        int tmp = prev;
        prev = now; now = now + (now-tmp) + 8;
    }
    board.erase(remove(board.begin(), board.end(), -1), board.end()); //정리
    while(board.size() != N*N) {
        board.push_back(0);
    }
}

void explode(vector<int>& board, int N) {
    bool exploded = true;
    while(exploded) {
        exploded = false;
        int prev = 0; int combo;
        for(int i=1; i<N*N; i++) {
            int now = board[i];
            if(now == 0) break;
            if(now == prev) {
                combo += 1;
                if(combo == 4) {
                    board[i] = -1; board[i-1] = -1; board[i-2] = -1; board[i-3] = -1;
                    exploded = true;
                    answer += now*combo;
                }
                else if(combo > 4) {
                    board[i] = -1;
                    answer += now;
                }
            }
            else {
                combo = 1;
            }
            prev = now;
        }
        board.erase(remove(board.begin(), board.end(), -1), board.end()); //정리
        while(board.size() != N*N) {
            board.push_back(0);
        }
    }
}

void change(vector<int>& board, int N) {
    vector<int> new_board;
    new_board.push_back(0);
    int prev = board[1]; int combo = 1;
    if(prev != 0) {
        for(int i=2; i<N*N; i++) {
            if(board[i] == 0 || new_board.size() > N*N) break;
            if(prev == board[i]) {
                combo += 1;
            }
            else {
                //grouped
                new_board.push_back(combo); new_board.push_back(prev);
                combo = 1;
            }
            prev = board[i];
        }
        new_board.push_back(combo); new_board.push_back(prev);
    }
    while(new_board.size() > N*N) {
        new_board.pop_back();
    }
    while(new_board.size() < N*N) {
        new_board.push_back(0);
    }
    board = new_board;
}

int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int N, M; answer = 0;
    cin >> N >> M;
    vector<vector<int> > twoD(N, vector<int>(N, 0));
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin >> twoD[i][j];
        }
    }


    vector<int> board;
    board.push_back(twoD[N/2][N/2]);
    // 2, 2, 2, 2, 4, 4, 4, 4, 6, 6, 6, 6, n은 홀수이므로 n-1까지
    int start_x = N/2; int start_y = N/2-1;
    for(int i=2; i<N; i+=2) {
        //down
        for(int j=0; j<i; j++) {
            board.push_back(twoD[start_x][start_y]);
            start_x += 1;
        }
        start_x -= 1; start_y += 1;
        //right
        for(int j=0; j<i; j++) {
            board.push_back(twoD[start_x][start_y]);
            start_y += 1;
        }
        start_x -= 1; start_y -= 1;
        //up
        for(int j=0; j<i; j++) {
            board.push_back(twoD[start_x][start_y]);
            start_x -= 1;
        }
        start_x += 1; start_y -= 1;
        //left
        for(int j=0; j<i; j++) {
            board.push_back(twoD[start_x][start_y]);
            start_y -= 1;
        }
    }

    for(int i=0; i<M; i++) {
        int si, di;
        cin >> di >> si;
        do_magic(board, N, si, di);
        explode(board, N);
        change(board, N);
    }

    cout << answer << endl;
    return 0;
}