[백준/BOJ] 20056 마법사 상어와 파이어볼

문제 : 20056 마법사 상어와 파이어볼

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

N 제한이 50, K제한이 1000밖에 안되므로 그냥 구현 문제이다.

구현 시 파이어볼 합쳐졌을 때의 관리가 어려우므로

미리 나누어 놓지 말고 합쳐만 놓았다가 나중에 이동해야 할 때

방향을 정해 큐에 다시 넣어주는 것이 코드를 짜기 편하다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct ABC{
    ll R, C, M, S, D, now; // now는 그 칸의 파이어볼 개수를 나타내는 변수
    ABC() {}
    ABC(ll R, ll C, ll M, ll S, ll D, ll now): R(R), C(C), M(M), S(S), D(D), now(now) {}
};
ll N, M, K, ans, dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
ABC arr[55][55];
queue<ABC> q;
void f(){
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            if (arr[i][j].now)
                q.push(arr[i][j]);
            arr[i][j]=ABC(0,0,0,0,0,0);
        }
    }
    while (!q.empty()){
        ABC x=q.front();
        q.pop();
        if (x.M==0)
            continue;
        if (x.now>1){ // 만약 합쳐져 있다면 쪼개서 다시 큐에 넣음
            ll chk=x.D;
            x.M/=5;
            x.S/=x.now;
            x.now=1;
            for (int i=0;i<4;i++){
                if (chk==-1)
                    x.D=i*2+1;
                else
                    x.D=i*2;
                q.push(x);
            }
            continue;
        }
        ll dr=(x.R+dir[x.D][0]*x.S)%N, dc=(x.C+dir[x.D][1]*x.S)%N;
        if (dr<0)
            dr+=N;
        if (dc<0)
            dc+=N;
        if (arr[dr][dc].now==0)
            arr[dr][dc]=ABC(dr,dc,x.M,x.S,x.D,1);
        else{ // 이미 다른 파이어볼이 있는 경우
            arr[dr][dc].M+=x.M;
            arr[dr][dc].S+=x.S;
            if (arr[dr][dc].D%2!=x.D%2) // 방향이 모두 홀수 or 모두 짝수인지 판별
                arr[dr][dc].D=-1;
            arr[dr][dc].now++;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M >> K;
    for (int i=0;i<M;i++){
        ll r, c, m, s, d;
        cin >> r >> c >> m >> s >> d;
        arr[r-1][c-1]=ABC(r-1,c-1,m,s,d,1);
    }
    while (K--) // K번 이동 실행
        f();
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            if (arr[i][j].now==1)
                ans+=arr[i][j].M;
            else // 합쳐져 있는 파이어볼인 경우
                ans+=arr[i][j].M/5*4;
        }
    }
    cout << ans;
    return 0;
}