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

[문제]

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

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

 

[풀이]

 

N*N 격자에 파이어볼 M개가 존재한다.

각 파이어볼은 질량(m), 속력(s), 방향(d)을 가지고 있다.

 

1. 모든 파이어볼이 d 방향으로 s만큼 움직인다,.

2. 2개 이상의 파이어볼이 있는 칸은 하나의 파이어볼로 합쳐진다.

 - 합쳐진 파이어볼은 4개의 파이어볼로 나뉘어진다.

- 각 파이어볼의 질량은 ( 합쳐진 파이어볼의 질량 합 / 5 )

- 각 파이어볼의 속력은 ( 합쳐진 파이어볼의 속력 합 / 파이어볼의 개수) 

- 모든 파이어볼의 방향이 홀수 또는 짝수로 일치할 경우 나뉘어진 파이어볼의 방향은 0,2,4,6이 되고 아닌 경우 1,3,5,7이 된다.

 

1번과 2번에 대해 각각의 api로 관리했다. 파이어볼이 이동하는 것은 moveBall에서 처리하고 파이어볼이 나뉘어 지는 것은 divideBall api에서 처리해주었다.

 

첫번째로 moveBall에서 파이어볼을 이동시켰다.

문제에서 주어진 조건으로 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다. 

 

따라서 (1,1)을 기준으로 시작하여 s%N 만큼 이동하도록 해주었다. 또한 이동한 위치가 1보다 작거나 N보다 클 경우 N만큼 빼주거나 더해주어 이동위치를 계산했다.

 

그리고 두번째로 이동한 파이어볼에 대해 문제 조건에 맞게 divideBall에서 파이어볼을 나눠주도록 처리했다.

 

 

[코드]

#include <iostream>
#include <vector>
#include <cmath>
#define MAX 51

using namespace std;

struct Ball{
    int m,s,d;
};
int N,M,K;
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

vector<Ball> fireBall[MAX][MAX];

void moveBall()
{
    vector<Ball> tmpBall[MAX][MAX];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            for(int k=0;k<fireBall[i][j].size();k++){
                int s= fireBall[i][j][k].s%N;
                int d= fireBall[i][j][k].d;
                
                int nx = i+dx[d]*s;
                int ny = j+dy[d]*s;
                
                
                if(nx < 1)   nx+=N;
                if(nx > N) nx -=N;
                
                if(ny < 1)   ny+=N;
                if(ny > N) ny-= N;
                
                tmpBall[nx][ny].push_back(fireBall[i][j][k]);
            }
        }
    }
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            fireBall[i][j].clear();
            fireBall[i][j] = tmpBall[i][j];
        }
    }
}

void divideBall()
{
    vector<Ball> tmpBall[MAX][MAX];

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if ( fireBall[i][j].size() == 1){
                tmpBall[i][j] = fireBall[i][j];
            }
            else if ( fireBall[i][j].size() >= 2){
                int totalS=0;
                int totalM=0;
                bool even=false;
                bool odd=false;
                
                for(int k=0;k<fireBall[i][j].size();k++){
                    int dir=fireBall[i][j][k].d;
                    if(dir % 2 == 0)    even = true;
                    else    odd = true;
                    
                    totalS+=fireBall[i][j][k].s;
                    totalM+=fireBall[i][j][k].m;
                }
                
                int m = totalM/5;
                int s = totalS/fireBall[i][j].size();
                int dir = even && odd ? 1 : 0;
                 if ( m > 0)
                 {
                     for(int d=dir;d<8;d+=2){
                        tmpBall[i][j].push_back({m,s,d});
                    }
                 }
            }
            fireBall[i][j].clear();
            fireBall[i][j] = tmpBall[i][j];
        }
    }
    
}

int main(void)
{
    ios::sync_with_stdio(false);
    
    cin >> N >> M >> K;
    
    for(int i=0;i<M;i++){
        int x,y,m,s,d;
        cin >> x >> y >> m >> s >> d;
        fireBall[x][y].push_back({m,s,d});
    }
    for(int i=0;i<K;i++){
        moveBall();
        divideBall();
    }
    
    long long totalM =0;
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            for(int k=0;k<fireBall[i][j].size();k++)    totalM+=fireBall[i][j][k].m;
        }
    }
    
    cout << totalM;
    return 0;
}