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

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

시뮬레이션, 구현

---

 

1. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
   • 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.
2. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
   1. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
   2. 파이어볼은 4개의 파이어볼로 나누어진다.
   3. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
      1. 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
      2. 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
      3. 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
   4. 질량이 0인 파이어볼은 소멸되어 없어진다.

 

설명을 그대로 구현하면 되는 문제이다. 

 

한 칸에 여러개의 공이 있을 수 있으므로 2차원벡터로 map을 설정했다.

 

그리고 공의 속력만큼 공이 이동하는데 1행은 N행과 연결되어있고, 1열은 N열과 연결되어 있으므로 방향을 따라서 순회한다고 생각했다. 그래서 도착지점을 한 번에 계산하도록 했다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
struct BALL{
    int mass, speed, dir;
};
 
int N, M, K;
vector<BALL> Map[51][51];
vector<BALL> tMap[51][51];
int dr[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dc[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
void input(){
    cin >> N >> M >> K;
    int r, c, m, s, d;
    for(int i = 0; i < M; i++){
        cin >> r >> c >> m >> s >> d;
        Map[r-1][c-1].push_back({m, s, d});
    }
}
 
void Move(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            for(auto &w: Map[i][j]){
                int nr = i + (w.speed % N) * dr[w.dir];
                int nc = j + (w.speed % N) * dc[w.dir];
                if(nr < 0)       nr = N + nr;
                else if(nr >= N) nr %= N;
                if(nc < 0)       nc = N + nc;
                else if(nc >= N) nc %= N;
                
                tMap[nr][nc].push_back({w.mass, w.speed, w.dir});
            }
            Map[i][j].clear();
        }
    }
}
 
void Divide(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(tMap[i][j].size() < 2) continue;
            int sum_mass = 0;
            int sum_speed = 0;
            int prev_dir = -1;
            bool issame = true;
            for(auto &w: tMap[i][j]){
                sum_mass += w.mass;
                sum_speed += w.speed;
                if(prev_dir == -1) prev_dir = w.dir;
                else if(prev_dir % 2 != w.dir % 2) issame = false;
            }
            int div_cnt = tMap[i][j].size();
            tMap[i][j].clear();
            if(sum_mass / 5 == 0) continue;
            for(int k = 0; k < 4; k++){
                if(issame) tMap[i][j].push_back({sum_mass/5, sum_speed/div_cnt, k*2});
                else       tMap[i][j].push_back({sum_mass/5, sum_speed/div_cnt, k*2 + 1});
            }
        }
    }
}
 
void CopyM(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            Map[i][j] = tMap[i][j];
            tMap[i][j].clear();
        }
    }
}
 
int Sum_of_Mass(){
    int sum_of_mass = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            for(auto &w: Map[i][j]){
                sum_of_mass += w.mass;
            }
        }
    }
    return sum_of_mass;
}
 
void solve(){
    while(K--){
        Move();
        Divide();
        CopyM();
    }
    cout << Sum_of_Mass() << "\n";
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}