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

www.acmicpc.net/problem/21611

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

 

백준 21610번 - 마법사 상어와 비바라기

백준 21608번 - 상어 초등학교

백준 21609번 - 상어 중학교

 

새로 올라온 삼성 4문제 중 구현 난이도가 가장 어려운 문제였습니다.

M개의 쿼리마다 주어지는 방향(d)과 거리(s)를 이용하여 블리자드 마법 시전시 수행되는 과정은 다음과 같습니다.

 

N=7일때, 구슬이 들어갈 칸의 인덱스 (순서)

1. d방향, 거리가 s이하인 모든 칸의 구슬을 파괴하며 파괴된 칸은 빈 칸이 된다.
2. 구슬이 파괴된 후에는 빈 칸이 생겨 다음 인덱스의 구슬들이 앞으로 당겨진다.
3. 4개이상의 연속된 같은 구슬들은 폭발하여 없어진다.
4. 폭발할 구슬이 없어질 때까지 2, 3을 반복한다.
5. 더 이상 폭발할 구슬이 없으면 구슬이 변화한다.

 

2,3의 과정을 구현하면서 칸의 인덱싱이 힘들었는데, 상어를 기준으로 위치가 바뀌는 방향의 순서가 ← , ↓ , → , ↑ 이고 방향이 2번 바뀔때마다 이동하는 칸이 1씩 증가하는 규칙을 이용했습니다.

위의 화살표가 표시된 그림을 보면 빨간색은 1칸, 노란색 2칸, 초록색3칸, 파란색4칸으로 방향이 2번 바뀔때마다 1칸씩 이동칸수가 한칸씩 증가하는것을 확인할 수 있습니다.

 

위에서 언급한 1~5의 과정을 토대로 간략하게 풀이과정을 설명하자면, 1의 과정을 magic 함수에서 수행하고

2의 당겨지는 과정 대신 빈칸을 제외한 구슬들을 순서대로 vector에 저장(saveBall함수)하여 explode함수에서 3,4의 과정을 수행하도록 했습니다. 더이상 폭발할 구슬이 없으면 change함수를 수행하며 결과로 주어진 구슬들을 배열에 인덱스 순서대로 업데이트하면 하나의 쿼리가 수행된 결과를 얻을 수 있습니다.

 

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
using namespace std;

int N,M,cnt=0, score=0;
int m[50][50]{};
vector<int> tmp; // 빈칸을 제외한 구슬들이 순서대로 저장됨
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};
int td[4] = {2,1,3,0};

void updateMap(){
    memset(m,0,sizeof(m));
    int cy,cx,d=0,t=1;
    cy = cx = N/2;
    int idx = 0;
    while(idx!=tmp.size()){
        for(int k=0; k<2; k++){
            for(int i=0; i<t; i++){
                int ny = cy + dy[td[d]];
                int nx = cx + dx[td[d]];
                m[ny][nx] = tmp[idx++];
                cy = ny;
                cx = nx;
                if(idx==tmp.size()) return;
            }
            d = (d+1)%4;
        }
        t++;
    }
}

void change(){
    vector<int> ttmp;
    int tt;
    for(int i=0; i<tmp.size(); i++){
        if(ttmp.size()>=N*N) break;
        tt = i;
        while(tmp[tt]==tmp[i] && tt<tmp.size()) tt++;
        int A=(tt-i), B=tmp[i];
        ttmp.push_back(A);
        ttmp.push_back(B);
        i = tt-1;
    }
    if(ttmp.size() >= N*N) // 구슬개수가 범위를 초과하면 개수를 맞춰 줌
        while(ttmp.size()>=N*N) ttmp.pop_back();
    tmp = ttmp;
    cnt = tmp.size();
}

void explode(){
    bool chk = true;
    while(chk){
        vector<int> ttmp;
        int tt;
        chk = false;
        for(int i=0; i<tmp.size(); i++){
            tt = i;
            while(tmp[tt]==tmp[i] && tt<tmp.size()) tt++;
            if(tt-i<4) {
                for(int j=i; j<tt; j++){
                    ttmp.push_back(tmp[i]);
                }
            } else {
                score += tmp[i]*(tt-i); // 폭발한 구슬 점수 업데이트
                chk = true;
            }
            i = tt-1;
        }
        tmp = ttmp;
    }
}

void saveBall(){
    tmp.clear();
    int cy,cx,d=0,t=1;
    cy = cx = N/2;

    int idx = 0;
    while(idx!=cnt){
        for(int k=0; k<2; k++){
            for(int i=0; i<t; i++){
                int ny = cy + dy[td[d]];
                int nx = cx + dx[td[d]];
                if(m[ny][nx]) {
                    tmp.push_back(m[ny][nx]);
                    idx++;
                }
                cy = ny;
                cx = nx;
                if(idx==cnt) return;
            }
            d = (d+1)%4;
        }
        t++;
    }
}

void magic(int d, int s){
    for(int i=1; i<=s; i++){
        int ny = N/2 + i*dy[d];
        int nx = N/2 + i*dx[d];
        if(m[ny][nx]==0) continue;
        m[ny][nx] = 0;
        cnt--;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>M;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin>>m[i][j];
            if(m[i][j]) cnt++;
        }
    }

    int d, s;
    for(int i=0; i<M; i++){
        cin>>d>>s; d--;
        magic(d,s);
        saveBall();
        explode();
        change();
        updateMap();
    }
    
    cout<<score;
}