(C++) - 백준(BOJ) 20056번 : 마법사 상어와 파이어볼

www.acmicpc.net/problem/20056

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

구현문제였습니다.

 

풀이방법

 1. 파이어볼은 행,열,질량,속도,방향 5개의 정보를 포함하고 있습니다. 구조체를 이용해줍니다. 해당 구조체들을 원소로 파이어볼들의 정보를 담은 vector 변수 fireBalls, 격자의 정보를 저장할 vector변수 board를 선언해줍니다. 그리고 8방향을 표현할 dx,dy배열, 모두 홀수또는 짝수 방향일 때 분산시킬 방향의 정보를 담는 oddEvendir, 아닌 경우 elseDir배열로 방향의 정보를 담았습니다. 

 

 2. k만큼 다음을 수행합니다. 

    2-1. 파이어볼 이동 : 먼저 board의 정보를 갱신하기 위해 들어있는 파이어볼들을 없애줍니다. 그 후 fireBall의 size만큼 loop를 돌면서 방향,속도로 다음 위치를 계산해 행,열을 갱신해줍니다. 그 후 board에 갱신된 위치의 파이어볼 정보를 넣어줍니다.

 

    2-2. 파이어볼 합치고 분산 : fireBalls 배열을 갱신해주기 위해 같은크기, 자료형의 tmp를 선언해줍니다. board를 검사하면서 해당 위치의 모든 파이어볼을 합쳐줍니다. i행 j열에 파이어볼이 하나도 없으면 아무일도 없으므로 continue, 1개만 있으면 tmp에 push해줍니다. 나머지의 경우는 합쳐지거나 나눠져야 합니다. i,j에 존재하는 k개의 파이어볼들에 대해 loop를 돌며 질량과 속력을 합쳐주고 주어진 공식을 이용해 새롭게 만들어진 질량과 속도를 구할 수 있습니다. 또한 모두 홀수방향인지 짝수방향인지 여부도 확인해줍니다. 그 후 나눠줍니다. 5로 합친 질량을 나누었을 때 질량이 0이라면 파이어볼이 없어진 것이므로 continue해줍니다. 흩어지는 방향에 따라 tmp에 나눠지는 파이어볼들을 넣어줍니다.

 

3. 정답출력 : fireBalls의 size만큼 질량을 다 더해줍니다. 그 후 출력합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int n,m,k,ans;
int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};
int oddEvenDir[] = {0,2,4,6};
int elseDir[] = {1,3,5,7};
struct info{ int x, y, weight, speed, dir; };

vector <info> fireBalls;
vector <info> board[51][51];

void moveBalls(){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) 
            board[i][j].clear();

    for(int i = 0; i < fireBalls.size(); i++){
        int x = fireBalls[i].x;
        int y = fireBalls[i].y;
        int weight = fireBalls[i].weight;
        int speed = fireBalls[i].speed;
        int dir = fireBalls[i].dir;
        int move = speed % n;

        int nx = x + dx[dir] * move;
        int ny = y + dy[dir] * move;
        if (nx > n) nx -= n;
        if (ny > n) ny -= n;
        if (nx < 1) nx += n;
        if (ny < 1) ny += n;
        fireBalls[i].x = nx;
        fireBalls[i].y = ny;
        board[nx][ny].push_back({ nx,ny,weight,speed,dir });
    }
}

void sumAndDivBalls(){
    vector<info> tmp;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            if (board[i][j].size() == 0) continue;
            if (board[i][j].size() == 1){
                tmp.push_back(board[i][j][0]);
                continue;
            }
            
            int weightSum = 0;
            int speedSum = 0;
            int ballsCnt = board[i][j].size();
 
            bool isEven = true;
            bool isOdd = true;
            
            for (int k = 0; k < board[i][j].size(); k++){
                weightSum += board[i][j][k].weight;
                speedSum += board[i][j][k].speed;
                if (board[i][j][k].dir % 2 == 0) isOdd = false;
                else isEven = false;
            }
            
            int mass = weightSum / 5;
            int speed = speedSum / ballsCnt;
            if (!mass) continue;
            if (isEven == true || isOdd == true){
                for (int k = 0; k < 4; k++) tmp.push_back({ i, j, mass, speed, oddEvenDir[k] });
            }
            else{
                for (int k = 0; k < 4; k++) tmp.push_back({ i, j, mass, speed, elseDir[k] });
            }
        }
    }
    fireBalls = tmp;
}


int main(){
    cin >> n >> m >> k;
    for(int i = 0; i < m; i++){
        int r,c,m,s,d;
        cin >> r >> c >> m >> s >> d;
        fireBalls.push_back({r,c,m,s,d});
        board[r][c].push_back({r,c,m,s,d});
    }

    while(k--){
        moveBalls();
        sumAndDivBalls();
    }

    for(int i = 0; i < fireBalls.size(); i++) ans += fireBalls[i].weight;
    cout << ans <<'\n';
}