[백준 21611][C++] 마법사 상어와 블리자드

문제

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

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

 

풀이 과정

1. 중간을 기준으로 달팽이 모양으로 좌표를 미리 벡터에 저장해놓는다. 이후의 탐색은 해당 벡터를 이용한다.

2. d와 s를 이용하여 블리자드를 통해 구슬을 파괴한다.

3. 칸에 빈칸이 존재하면 앞으로 당겨온다.

4. 같은 칸이 4칸 이상 지속되면 폭발시킨다. (폭발 후 빈칸이 발생하면 3번 함수를 이용한다)

5. 더 이상의 폭발이 없다면 달팽이 모양으로 탐색하며 칸의 모양을 파악하며 새로운 형태로 변형한다.

6. 2-5 과정을 M번 반복하고 최종 점수의 합을 출력한다.

 

 

 

세부 풀이

이 문제를 풀면서 가장 중요한 부분은 달팽이 모양의 좌표를 미리 저장하는 개념과, 그 벡터를 이용해서 탐색하는 것이라고 생각한다. 달팽이 모양의 좌표를 미리 벡터에 저장하도록 구현하는 함수를 필자가 느낀 대로 작성했는데, 더 나은 풀이가 있는지 찾아보고  추가할 예정이다.

 

(1) make_position 함수

이 문제의 핵심이라고 볼 수 있는 함수이다. 필자는 1칸, 2칸 2칸, 3칸, 3칸, 4칸 4칸,... 씩 전진하며 달팽이 모양을 탐색하도록 구현했다.

그림으로 나타내면 아래와 같다.

 

첫 1칸과 마지막 N길이의 칸은 1번씩만 이용되며 나머지 칸들은 2번씩 사용되는 규칙을 찾았다. 따라서 1칸 크기의 탐색 후, 2칸 크기의 탐색 2번, 3칸 크기의 탐색 2번, 4칸 크기의 탐색 2번,... 과 같은 과정을 거쳐 입력받은 N크기의 배열을 탐색하도록 구현했다. 이때 idx를 나머지 연산 처리해 규칙적으로 반복되게 구현했다.

 

(2) blizzard 함수

간단히 d와 s를 입력받고 s 길이만큼 d 방향으로 존재하는 블록을 지우는 함수이다.

 

(3) reload 함수

해당 함수는 blizzard 이후에도 수행되고, 폭발 이후에도 사용된다.

make_position 함수로 position 벡터에 저장한 값을 이용한다. 달팽이 모양으로 탐색하는데 0인 경우는 무시하고 0이 아닌 값만 새로운 벡터인 values에 담는다. 0을 제거한 길이는 원래 길이보다 작거나 같으므로, 해당 값이 남아있는 것을 막기 위해 map을 초기화한다. 초기화 후에 values에 담긴 값을 다시 달팽이 모양으로 탐색하며 저장한다.

 

(4) explosion 함수

달팽이 모양으로 탐색하며 탐색하는 값을 벡터에 저장하며 진행하는데, 이때 길이가 4보다 작을 때 값이 변경되었다면 별다른 처리 없이 벡터를 초기화하며 새로운 값을 넣고, 4보다 크거나 같을 때 값이 변경되었다면 폭발시킨 후 새로운 입력을 받기 시작하도록 구현했다. 자세한 내용은 소스코드에 적힌 주석을 참고하면 이해가 도움이 될 것이다.

return 값은 flag를 통해 폭발이 있었다면 true를 반환하고, 폭발이 없었다면 false를 반환하도록 구현했다.

 

(5) change 함수

달팽이 모양으로 탐색하며 연속된 수의 개수, 연속된 수의 타입으로 2칸씩 추가하는 함수이다. 연속되면 cnt를 증가시키고 연속되지 않을 때 cnt와 이전에 저장돼있던 값을 2개 벡터에 저장한다. 모든 탐색이 끝난 후 달팽이 모양으로 다시 map을 채운다. 이때 더 길이가 짧을 수 있어서 memset을 추가했다. change 이후 길이가 원래보다 더 길어질 수 있는데, 이때 범위 처리를 하지 않으면 index를 벗어나 오류가 발생할 수 있다. 따라서 N*N 보다 작을 때까지만 탐색하도록 조건문을 통해 제한했다.

 

(6) solve 함수

입력받았던 d와 s를 이용해 blizzard를 수행한 뒤, reload를 수행한다.

이후 explosion 함수를 더 이상의 폭발이 없을 때까지 수행하며 reload를 같이 진행한다.

모든 폭발이 완료되면 change를 진행한다.

위 과정을 입력받은 M개의 case 상황을 모두 수행하고 얻은 점수를 출력한다.

 

소스 코드

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

int N, M, ans;
const int max_n = 51;
int map[max_n][max_n];

int dir[5][2]={{0,0},{-1,0},{1,0},{0,-1},{0,1}};
vector<pair<int,int>> position;
vector<pair<int,int>> magic;

void make_position(int n){
    int mk_poistion_dir[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
    int d=1;
    int idx=0;
    int x=(n+1)/2;
    int y=(n+1)/2;

    //상어 위치 입력
    position.push_back({x,y});
    //다음 위치 이동 후 방향 전환
    x+=mk_poistion_dir[idx][0];
    y+=mk_poistion_dir[idx][1];
    idx++;

    //1칸 짜리 입력
    position.push_back({x,y});
    //다음 위치 이동후 방향 전환 + 길이 증가
    x+=mk_poistion_dir[idx][0];
    y+=mk_poistion_dir[idx][1];
    idx++;
    d++;

    //이후 같은 길이로 두번씩 반복된다.
    while(d<n){
        for(int i=0;i<d;i++){
            int nx = x + mk_poistion_dir[idx][0]*i;
            int ny = y + mk_poistion_dir[idx][1]*i;
            position.push_back({nx,ny});
            if(i==d-1) {
                x=nx+mk_poistion_dir[idx][0]; 
                y=ny+mk_poistion_dir[idx][1];
            }
        }

        idx=(idx+1)%4;

        for(int i=0;i<d;i++){
            int nx = x + mk_poistion_dir[idx][0]*i;
            int ny = y + mk_poistion_dir[idx][1]*i;
            position.push_back({nx,ny});
            if(i==d-1) {
                x=nx+mk_poistion_dir[idx][0]; 
                y=ny+mk_poistion_dir[idx][1];
            }
        }

        idx=(idx+1)%4;
        d++;
    }

    //마지막 부분은 한번 수행된다.
    for(int i=0;i<d;i++){
        int nx = x + mk_poistion_dir[idx][0]*i;
        int ny = y + mk_poistion_dir[idx][1]*i;
        position.push_back({nx,ny});
        if(i==d-1) {
            x=nx+mk_poistion_dir[idx][0]; 
            y=ny+mk_poistion_dir[idx][1];
        }
    }

}

void Input(){
    cin >> N >> M;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cin >> map[i][j];
        }
    }
    make_position(N);
    int d,s;
    for(int i=0;i<M;i++){
        cin >> d >> s;
        magic.push_back({d,s});
    }
}


void blizzard(int d, int s){
    int x=position[0].first;
    int y=position[0].second;
    for(int i=1;i<=s;i++){
        x+=dir[d][0];
        y+=dir[d][1];
        map[x][y]=0;
    }
}

void reload(){
    vector<int> values;
    for(int i=0;i<position.size();i++){
        int x=position[i].first;
        int y=position[i].second;
        if(map[x][y]==0) continue;
        values.push_back(map[x][y]);
    }

    memset(map,0,sizeof(map));

    for(int i=0;i<values.size();i++){
        int x=position[i+1].first;
        int y=position[i+1].second;
        map[x][y]=values[i];
    }
}


bool explosion(){
    bool flag = false;
    vector<pair<int,int>> del_list;
    int del_v = 0;
    del_list.clear();
    for(int i=1;i<position.size();i++){
        int x=position[i].first;
        int y=position[i].second;
        //비어있으면 그냥 넣는다
        if(del_list.empty()){
            del_v = map[x][y];
            del_list.push_back({x,y});
        }
        //비어있지 않으면 들어있는 값과 비교
        else{
            //일치하면 넣는다.
            if(del_v == map[x][y]){
                del_list.push_back({x,y});
            }
            //일치하지 않으면 새로운 벡터로 만들어야한다.
            //지금까지 저장된 수를 확인해서 처리한다.
            else{
                if(del_list.size()>=4){
                    for(int j=0;j<del_list.size();j++){
                        int nx=del_list[j].first;
                        int ny=del_list[j].second;
                        map[nx][ny]=0;
                    }
                    ans += del_list.size() * del_v;
                    flag = true;
                }

                del_list.clear();
                del_v= map[x][y];
                del_list.push_back({x,y});
            }
        }
    }
    return flag;
}

void change(){
    vector<int> temp;
    int v = map[position[1].first][position[1].second];
    int cnt = 1;
    for(int i=2;i<position.size();i++){
        int x=position[i].first;
        int y=position[i].second;
        if(map[x][y]==v){
            cnt++;
        }
        else{
            temp.push_back(cnt);
            temp.push_back(v);
            v = map[x][y];
            cnt=1;
        }
    }
    memset(map,0,sizeof(map));
    for(int i=0;i<temp.size();i++){
        //범위 조심. 그 이상 담긴 것은 버린다.
        if(i+1>=N*N) break;
        int x=position[i+1].first;
        int y=position[i+1].second;
        map[x][y]=temp[i];
    }
}

void solve(){
    for(int i=0;i<M;i++){
        int d = magic[i].first;
        int s = magic[i].second;
        blizzard(d,s);
        reload();
        while(true){
            if(!explosion()) break;
            reload();
        }
        change();
    }

    cout << ans;
}

int main(){
    Input();
    solve();
    return 0;
}

//함수 구현이 잘 되었는지 체크할때 사용했던 함수
void print_map(){
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

void check_mkposi(){
    int num=1;
    for(int i=0;i<N*N;i++){
        int x = position[i].first;
        int y = position[i].second;
        map[x][y] = num;
        num++;
    }
    print_map();
}

 

 

결과 및 후기