[백준 20056][C++] 마법사 상어와 파이어볼

문제

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

20056번: 마법사 상어와 파이어볼

 

풀이 과정

1. 파이어볼의 정보를 담을 구조체 생성, 파이어볼을 각 위치의 queue에 저장하도록 구현

2. 각 인덱스의 queue를 방문하여 존재하는 모든 파이어볼의 이동을 수행하는 함수 구현

3. 이동 후 2개 이상의 파이어볼이 있는 칸은 합쳐지고 나뉘는 과정을 거친다.

4. 2-3 과정을 K번 반복한 뒤 모든 queue에 있는 파이어볼의 질량의 합을 출력한다.

 

 

세부 풀이

(1)

입력받는 N의 사이즈에 맞게 queue를 생성한다.(Line 14) 따라서 위치정보는 queue가 위치하는 index가 되므로 파이어볼 구조체에서는 행과 열 정보를 제외시켰다.

 

(2) move 함수

이중 for문을 통해 방문하는 index에 위치하는 queue에 들어있는 모든 파이어볼들을 이동시키는 함수이다. 이때 queue에서 꺼내서 이동된 파이어볼이 중복하여 이동하는 것을 방지하기 위해, (Line 28) new_q를 생성하여 이동시킨 파이어볼을 new_q에 저장했고 함수의 끝 부분에서 q를 new_q로 업데이트하는 방식으로 동작한다.

 

이동할 새로운 위치를 지정할 때 한 칸씩 이동하는 것이 아니라 나머지 연산을 통해 최종적으로 이동할 위치를 구한 뒤 한 번에 이동시켜주는 방식을 이용했다.

 

(3) sum_divide 함수

이중 for문을 통해 방문하여 queue에 2개 이상의 파이어볼이 들어있다면 문제 조건에 맞게 더한 뒤 4방향으로 나누어 저장하는 함수이다. 4방향으로 나눈 파이어볼은 다시 해당 위치에 push 하여 다음 이동을 기다린다.

 

이때 모두 짝수이거나 홀수인 경우를 탐지하기 위하여, 짝수의 개수를 구하여 짝수의 개수가 0인 경우(모두 홀수인 경우)와 짝수의 개수가 queue.size()인 경우(모두 짝수인 경우)에는 0,2,4,6 방향으로 설정하였다.

 

(4)

2-3 과정을 K번 반복하여, 모든 queue를 방문하여 질량을 더한 뒤 출력한다.

 

 

 

소스 코드

#include <iostream>
#include <queue>

using namespace std;

int N,M,K;
const int max_n = 52;
int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};

struct fire_ball{
    int m,d,s;
};

queue<fire_ball> q[max_n][max_n];

void Input(){
    cin >> N >> M >> K;
    for(int i=0;i<M;i++){
        fire_ball fb1;
        int r, c;
        cin >> r >> c >> fb1.m >> fb1.s >> fb1.d;
        q[r][c].push(fb1);
    }
}


void move(){
    queue<fire_ball> new_q[max_n][max_n];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            while(!q[i][j].empty()){
                // cout << "i : " << i << " j : " << j << ' ';
                fire_ball fb1;
                fb1 = q[i][j].front();
                q[i][j].pop();
                int newi, newj;
                int speed = fb1.s%N;
                newi = (i+dir[fb1.d][0]*speed + N)%N;
                if(newi==0) newi=N;

                newj = (j+dir[fb1.d][1]*speed + N)%N;
                if(newj==0) newj=N;

                // cout << "newi : " << newi << " newj : " << newj << '\n';
                new_q[newi][newj].push(fb1);
            }
        }
    }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            q[i][j]=new_q[i][j];
        }
    }
}

void sum_divide(){
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(q[i][j].size()>=2){
                int even_cnt = 0;
                int num_fb = q[i][j].size();
                int sum_mass = 0;
                int sum_speed = 0;
                while(!q[i][j].empty()){
                    fire_ball fb1 = q[i][j].front();
                    q[i][j].pop();

                    sum_speed += fb1.s;
                    sum_mass += fb1.m;

                    if(fb1.d%2==0) even_cnt++;
                }

                int each_mass = sum_mass/5;
                if(each_mass==0) continue;

                int each_speed = sum_speed/num_fb;

                int each_dir[4] = {1,3,5,7};
                if(even_cnt == 0 || even_cnt == num_fb){
                    for(int k=0;k<4;k++){
                        each_dir[k]--;
                    }
                }

                for(int k=0;k<4;k++){
                    fire_ball fb1;
                    fb1.d = each_dir[k];
                    fb1.m = each_mass;
                    fb1.s = each_speed;
                    q[i][j].push(fb1);
                }
            }
        }
    }    
}

void solve(){
    while(K--){
        move();
        sum_divide();
    }
    int sum=0;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            while(!q[i][j].empty()){
                fire_ball fb1 = q[i][j].front();
                q[i][j].pop();
                sum += fb1.m;
            }
        }
    }

    cout << sum;
}

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

 

결과 및 후기