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

문제 링크

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

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

 

풀이

격자의 각 칸을 Node 구조체로, 현재 단계에 존재하는 파이어 볼을 Ball 구조체로 관리합시다. 각 구조체는 다음처럼 이루어져 있습니다.

Ball
    - int x, y, w, d, s // 현재 좌표(x, y), 무게(w), 방향(d), 속력(s)
    - pair<int, int> move() // 공의 방향으로 s만큼 이동한 뒤 곳의 좌표를 반환
    
Node {
    - int w, s; // 해당 node에 도착한 파이어 볼들의 무게, 속도 합
    - vector<int> ds; // 해당 node에 도착한 파이어 볼들의 방향을 리스트로 관리

    - void add(Ball &ball) // 공이 node에 도착한 경우 추가해줌
    - void splitBalls(vector<Ball> &balls, int x, int y) // 규칙에 따라 4개의 파이어 볼을 생성
    - int getDelta() // node 내 모든 공의 방향이 짝수이거나 홀수이면 0을 반환, 그렇지 않으면 1을 반환
    - void clear() // node 초기화

1) 공을 이동시키고 node에 add() 합니다.

2) 각 node마다 공을 분할합니다.

 

자세한 구현은 코드를 참고해주세요.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int n, m, k;

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

struct Ball {
    int x, y, w, d, s;

    Ball(int x = 0, int y = 0, int w = 0, int d = 0, int s = 0) : x(x), y(y), w(w), d(d), s(s) {}

    pii move() {
        int curx = x, cury = y;
        curx += s * dx[d], cury += s * dy[d];
        curx %= n, cury %= n;
        return {(curx + n) % n, (cury + n) % n};
    }
};

struct Node {
    int w, s;
    vector<int> ds;

    Node(int w = 0, int s = 0) : w(w), s(s) {}

    void add(Ball &ball) {
        w += ball.w;
        s += ball.s;
        ds.push_back(ball.d);
    }

    void splitBalls(vector<Ball> &balls, int x, int y) {
        int cnt = ds.size();
        if (cnt == 0) return;
        else if (cnt == 1) {
            balls.emplace_back(x, y, w, ds.front(), s);
            return;
        }
        int ballWeight = w / 5;
        int ballSpeed = s / cnt;

        if (ballWeight == 0) return;

        int delta = getDelta();
        for (int i = 0; i < 4; i++) {
            balls.emplace_back(x, y, ballWeight, 2 * i + delta, ballSpeed);
        }
    }

    int getDelta() {
        int odd = 0, even = 0;
        for (int d: ds) {
            if (d & 1) odd++;
            else even++;
        }
        int delta = !(odd == 0 || even == 0);
        return delta;
    }

    void clear() {
        w = s = 0;
        ds.clear();
    }
};


vector<vector<Node>> board;
vector<Ball> balls;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    board.resize(n, vector<Node>(n));
    while (m--) {
        int r, c, w, s, d;
        cin >> r >> c >> w >> s >> d;
        balls.emplace_back(r - 1, c - 1, w, d, s);
    }
    while (k--) {
        for (Ball &ball: balls) {
            auto[x, y] = ball.move();
            board[x][y].add(ball);
        }
        balls.clear();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Node &node = board[i][j];
                node.splitBalls(balls, i, j);
                node.clear();
            }
        }
    }
    int ans = 0;
    for (Ball &ball: balls) {
        ans += ball.w;
    }
    cout << ans;
}