[백준] 21161. 마법사 상어와 블리자드(C++)

[문제]

 

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

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

 

[풀이]

 

1. 상어가 구슬 파괴
2. 구슬 이동
3. 구슬 폭발
   
   1. 4개 이상 연속하는 구슬
4. 구슬 이동
5. 구슬 변화
   1. 하나의 그룹 => 구슬 A,B (  A는 구슬의 개수 , B는 구슬 번호)

위와 같은 과정이 M번 반복해서 일어난다.

1번부터 5번까지의 각 과정을 api로 분리하여 구현했다.

 

상어가 구슬을 파괴하는 과정은 destruct_bead , 구슬이 이동하는 과정은 move_bead, 구슬이 폭발 후 이동하는 과정은  explode_bead, 구슬이 변화하는 과정은 change_bead에서 처리하도록 구현했다. 

 

또한 모든 과정이 달팽이 모양 회전을 기반으로 발생한다.

 

첫번째로 상어가 구슬을 파괴하는 과정은 현재 상어 위치를 기반으로 d 방향으로  s 거리만큼에 존재하는 구슬을 파괴하므로 for 문을 통해 간단하게 구할 수 있다. 

 

두번째로 구슬이 이동하는 과정을 달팽이 모양을 기반으로 회전한다. 또한 회전하는 길이가 1,1,2,2,3,3,4,4,5,5,... 이런식으로 2번씩 같은 길이를 반복하고 방향이 바뀌면서 길이가 +1이 되는 구조이다. 따라서 이중 for문의 바깥 for문에서는 2번을 count 해주고 내부 for문에서는 len 만큼 반복할 수 있도록 처리해줬다. 현재 길이를 두번 다 돌면 길이를 +1 해주도록 처리했고 영역을 벗어나는 경우에 while문을 빠져나오도록 조건을 걸었다. 달팽이 방향으로 한칸씩 다 돌면서 bead라는 일차원 배열을 선언하여 map에서 0이 아닌 값들에 대해서만 옮겨준다. 모든 map에 대해 한바퀴 다 돌고 나면 기존 map을 0으로 초기화 해주고 bead에 존재하는 값들을 복사해준다. 이때도 마찬가지로 달팽이 방향으로 회전하도록 했다.

 

세번째로 4개 이상 동일한 구슬이 반복되는 것에 대해 그룹화 하여 폭발시켜줬다. 이 때 문제에서 출력해야 되는 것은 폭발된 구슬의 개수이므로 explode_cnt라는 배열을 선언하여 각 구슬별 폭발된 개수를 저장해놨다. 구슬 이동과 마찬가지로 하나의 길이에 대해 두번씩 카운트 하면서 길이를 +1씩 해주었다. 이와 같이 달팽이 방향으로 돌면서 연속하는 구슬이 4개 이상인 경우 폭발 시켜줬다. bead 라는 벡터를 선언하여 폭발되지 않은 구슬만 담아줬다. 이런식으로 폭발할 구슬을 찾으면 한번 더 확인을 해줘야한다. 예를들어 구슬이 111222211111 이렇게 있으면 bead라는 벡터에 11111111이 존재하는데 이것도 연속된 구슬이 4개 이상이므로 폭발해야 하는 구슬이다. 따라서 bead에 대해서 한번 더 돌면서 연속되는 구슬이 있는지 확인해주고 update_bead 라는 벡터에 담아줬다.. 원래 구슬 폭발 후 바로 이동을 해야하는데 모든 그룹에 대해 폭발을 다 하고 이동하는식으로 구현해서 이렇게 된 것 같다. 이 부분에 대해서는 한번 더 고려해봐야겠다. 이렇게 구슬을 폭발하고  update_bead에 존재하는 구슬을 달팽이 방향으로 map에 옮겨줬다.

 

마지막으로 구슬을 그룹화하여 구슬 개수, 구슬 번호로 구슬을 change 해줬다. 여기서도 마찬가지로 달팽이 방향으로 돌면서 확인해줬다.

 

이와 같이 위의 방식을 M번 수행 후 각 구슬별 폭발된 구슬의 개수를  count 하여 출력해줬다.

 

유사 문제로는 

2022 상반기 오전 문제가 있는데 참고해보면 좋을 것 같다.

 

[코드]

 

#include <iostream>
#include <vector>
#include<string.h>
#define MAX 50

using namespace std;

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

int N,M;
int map[MAX][MAX]={0,};
int explode_cnt[4] = {0,};

void destruct_bead(int d,int s)
{
    int x = (N+1)/2;
    int y = (N+1)/2;
    
    for(int i=1;i<=s;i++){
        int nx = x + dx[d]*i;
        int ny = y + dy[d]*i;
        
        if( nx <= 0 || ny <= 0 || nx > N || ny > N )    break;
        map[nx][ny] =0;
    }
}

void move_bead()
{
    int tmp[MAX][MAX]={0,};
    
    int bead[MAX*MAX]={0,};
    int x= (N+1)/2;
    int y= (N+1)/2;
    int dir =3;
    int len = 1;
    int idx =0;
    bool flag=true;
    
    
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){
                x+=dx[dir];
                y+=dy[dir];
                
                if ( x <= 0 || y<= 0 || x > N || y > N ){
                    flag=false;
                    break;
                }
                
                if(map[x][y] != 0){
                    bead[idx] = map[x][y];
                    idx++;
                }
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
    x= (N+1)/2;
    y= (N+1)/2;
    dir =3;
    len = 1;
    idx =0;
    flag=true;
    
    
    for(int i=1;i<=N;i++){
        for(int j=0;j<=N;j++)   map[i][j]=0;
    }
               
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){
                x+=dx[dir];
                y+=dy[dir];
                
                if ( bead[idx] == 0){
                    flag=false;
                    break;
                }
                map[x][y] = bead[idx];
                idx++;
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
}

void explode_bead()
{
    int tmp[MAX][MAX]={0,};
    
    vector<int> bead;
    
    int x = (N+1)/2;
    int y = (N+1)/2;
    int dir =3;
    int len = 1;
    int idx =0;
    bool flag=true;
    
    
    int cur = -1;
    int cnt = 0;
    
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){

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

                if ( x <= 0 || y<= 0 || x > N || y > N || cur == 0){
                    flag=false;
                    break;
                }
                

                if(map[x][y] == cur){
                    cnt++;
                } else {
                    if( cnt >= 4 ){
                        explode_cnt[cur] += cnt;
                        for(int k=0;k<cnt;k++)  bead.pop_back();
                    }
                    cur = map[x][y];
                    cnt = 1;
                }
                bead.push_back(map[x][y]);
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
    vector<int> update_bead;
    
    cnt=0;
    cur = -1;
    while(1){
        bool duplicate = false;
        for(int i=0;i<bead.size();i++){
            if(bead[i] == cur){
                cnt++;
            } else {

                if( cnt >= 4 ){
                    duplicate= true;
                    explode_cnt[cur] += cnt;
                    for(int k=0;k<cnt;k++)  update_bead.pop_back();
                }
                cur = bead[i];
                cnt = 1;
            }
            update_bead.push_back(cur);

        }
        if( !duplicate )    break;
        else{
            bead.clear();
            bead = update_bead;
            update_bead.clear();
        }
    }
    
    x= (N+1)/2;
    y= (N+1)/2;
    dir =3;
    len = 1;
    idx =0;
    flag=true;
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){
                x+=dx[dir];
                y+=dy[dir];
                
                if ( idx == update_bead.size()){
                    flag=false;
                    break;
                }
                tmp[x][y] = update_bead[idx];
                idx++;
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)    map[i][j] = tmp[i][j];
    }
}

void bead_change()
{
    
    int tmp[MAX][MAX]={0,};
    
    vector<int> bead;
    
    int x = (N+1)/2;
    int y = (N+1)/2;
    int dir = 3;
    int len = 1;
    int idx = 0;
    bool flag=true;
    
    
    int cur = -1;
    int cnt = 0;
    
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){

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

                if ( x <= 0 || y<= 0 || x > N || y > N || cur == 0){
                    flag=false;
                    break;
                }

                if(map[x][y] == cur){
                    cnt++;
                } else {
                    if(cnt>0){
                        bead.push_back(cnt);
                        bead.push_back(cur);
                    }
                    cur = map[x][y];
                    cnt = 1;
                }
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
    x= (N+1)/2;
    y= (N+1)/2;
    dir =3;
    len = 1;
    idx =0;
    flag=true;
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){
                x+=dx[dir];
                y+=dy[dir];
                
                if (x <= 0 || y<= 0 || x > N || y > N || idx == bead.size()){
                    flag=false;
                    break;
                }
                tmp[x][y] = bead[idx];
                idx++;
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)    map[i][j] = tmp[i][j];
    }
    
}


int main(void)
{
    cin >> N >> M;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)    cin >> map[i][j];
    }
    
    for(int i=0;i<M;i++){
        int d,s;
        cin >> d >> s;
        destruct_bead(d,s);
        move_bead();
        explode_bead();
        bead_change();
    }
    
    cout << explode_cnt[1] * 1 + explode_cnt[2] * 2 + explode_cnt[3] * 3;
    return 0;
}