백준 20056번 - 마법사 상어와 파이어볼

www.acmicpc.net/problem/20056

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

아래의 주어진 과정을 그대로 코딩하면 되는 구현문제였습니다.

 

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

 

이동하기 전 파이어볼의 정보를 따로 저장해두고 이동시 배열의 해당 위치에 질량, 속력, 방향을 누적하여 저장했습니다.

위의 과정의 번호를 아래의 코드에 주석으로 표시해 뒀습니다.

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
using namespace std;

struct FireBall{
    int r,c,m,s,d;
    FireBall(int r=0, int c=0, int m=0, int s=0, int d=0):
    r(r), c(c), m(m), s(s), d(d){}
};

struct Info{
    int n,m,s,d;
    Info(int n=0, int m=0, int s=0, int d=0):
    n(n), m(m), s(s), d(d){}
};

int N,M,K;
Info m[51][51]{}; // 격자의 파이어볼 정보
vector<FireBall> fb; // 파이어볼 정보
int dy[8] = {-1,-1,0,1,1,1,0,-1};
int dx[8] = {0,1,1,1,0,-1,-1,-1};

// 2.
void update(){
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
        	// 2.에 해당하지 않는 경우
            if(m[i][j].n==1) {
                fb.emplace_back(FireBall(i,j, m[i][j].m, m[i][j].s, m[i][j].d));
            } 
            else if(m[i][j].n > 1){
            	// 2.3.
                int nm = m[i][j].m / 5;
                if(nm==0) continue; // 2.4.
                int ns = m[i][j].s / m[i][j].n;
                vector<int> nd(4);
                if(m[i][j].d == -1) nd = {1,3,5,7};
                else nd = {0,2,4,6};
                
                // 2.2.
                for(int k=0; k<4; k++){
                    fb.emplace_back(FireBall(i,j, nm, ns, nd[k]));
                }
            }
        }
    }
}

// 1.
void move(){
    memset(m,0,sizeof(m));
    for(auto val : fb){
    	// 음수가 안나올 만큼 적당한 값 더해줌(N*1000)
        int ny = (N*1000 + val.r + val.s * dy[val.d])%N;
        int nx = (N*1000 + val.c + val.s * dx[val.d])%N;
        
        // 2.1. (1. 포함)
        m[ny][nx].m += val.m;
        m[ny][nx].s += val.s;
        // 2.3.3. 전처리
        if(m[ny][nx].n == 0) m[ny][nx].d = val.d;
        else {
            if(m[ny][nx].d%2 != val.d%2) m[ny][nx].d = -1;
        }
        m[ny][nx].n++;
    }
    fb.clear();
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>M>>K;
    memset(m,0,sizeof(m));
    int r,c,m,s,d;
    for(int i=0; i<M; i++) {
        cin>>r>>c>>m>>s>>d;
        fb.emplace_back(FireBall(r,c,m,s,d));
    }
    
    while(K--){
        move();
        update();
    }

    int sum = 0;
    for(auto val : fb) sum += val.m;
    cout<<sum;
}