Algorithm) 백준 20056 마법사 상어와 파이어볼 c++

명령당 단계는 두단계로 이루어집니다

1. 파이어볼 이동

2. 파이어볼 분할

 

파이어볼은 좌표, 질량, 속도, 방향을 가지고 있기에 구조체를 만들어줬습니다.

그리고 한 좌표에 파이어볼이 여러개 들어갈 수 있기에 vector<FIREBALL>로 map을 만들고 파이어볼들을 관리할 fireball 벡터를 하나 만들었습니다.

 

나머지는 문제 그대로 구현 하면되는데 중요한점은 좌표가 n*n 맵 밖으로 나가게 되면 순환하게 되는 점입니다.

  int move = speed % n;
  int ny = cy + dy[direction] *move; 
  nt nx = cx + dx[direction] *move;
  if(ny<=0) ny += n;
  if(nx<=0) nx += n;
  if(ny>n) ny -= n;
  if(nx>n) nx -= n;

이 부분입니다. 만약 n이 4인데 speed가 5면 한바퀴 돌고 1만큼 더가겠죠? 그럼 한바퀴 도는건 알 필요가 없고 얼마만큼 더 가면 되냐만 알면 되기에 move = speed%n 연산을 해줬습니다.

 

위에 연산을 해도 만약 현재 x가 2인데 x방향으로 3만큼 가야하면 5가 되는 것처럼 한번 더 처리를 해줘야합니다

그래서 map을 벗어나는 좌표이면 n을 더해주거나 빼서 위치를 조정해주면 됩니다

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

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

struct FIREBALL {
    int y, x, m,d,s;
    FIREBALL(int ny, int nx, int nm, int ns, int nd) {
        y = ny;
        x = nx;
        m = nm;
        s = ns;
        d = nd;
    }
    FIREBALL();
};


int main() {
    int n,m,k;
    cin>>n>>m>>k;

    vector<FIREBALL> map[51][51];
    vector<FIREBALL> fireball;
    //입력
    for(int i=0; i<m; i++) {
        int y,x,m,d,s;
        cin>>y>>x>>m>>s>>d;
        fireball.push_back({y,x,m,s,d});
        map[y][x].push_back({y,x,m,s,d});
    }


    for(int K=0; K<k; K++) {

        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                map[i][j].clear();
            }
        }
        //이동
        for(int i=0; i<fireball.size(); i++) {
            int cy = fireball[i].y;
            int cx = fireball[i].x;
            int mass = fireball[i].m;
            int speed = fireball[i].s;
            int direction = fireball[i].d;

            int move = speed % n;
            int ny = cy + dy[direction] *move;
            int nx = cx + dx[direction] *move;

            if(ny<=0) ny += n;
            if(nx<=0) nx += n;
            if(ny>n) ny -= n;
            if(nx>n) nx -= n;

            map[ny][nx].push_back({ny,nx,mass,speed,direction});
            fireball[i].y=  ny;
            fireball[i].x = nx;
        }

        //분할
        vector<FIREBALL> tmp;
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(map[i][j].size()==0) continue;
                if(map[i][j].size()==1) {
                    tmp.push_back(map[i][j][0]);
                    continue;
                }
                int m_sum=0;
                int s_sum=0;
                bool odd = true;
                bool even = true;
                for(int t=0; t<map[i][j].size(); t++) {
                    if(map[i][j][t].d %2 == 1) even = false;
                    if(map[i][j][t].d %2 == 0) odd = false;
                    m_sum +=map[i][j][t].m;
                    s_sum +=map[i][j][t].s;
                }
                int children_m = m_sum/5;
                int children_s = s_sum/map[i][j].size();
                if(children_m ==0) continue;
                for(int t=0; t<4; t++) {
                    if(odd || even) {
                        tmp.push_back({i,j,children_m, children_s, t*2});
                    } else {
                        tmp.push_back({i,j,children_m, children_s, t*2 + 1});
                    }
                }
            }
        }
        fireball = tmp;
    }

    int ans = 0;
    for(int i=0; i<fireball.size(); i++) {
        ans+= fireball[i].m;
    }
    cout<<ans;

}