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

1. 입 출력

 

1) 입력

nxn 격자에 파이어볼 m개 발사

마법사 이동 k번 명령

N m k

m개의 줄에 i번 파이어볼에 대한 정보( 위치: R,c / 질량 : m / 속력 s / 방향 d )

4 2 1
1 1 5 2 2
1 4 7 1 6

2) 출력

남아있는 파이어볼 질량의 합을 출력

8

 

2. 문제 이해 

'1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다'

1행에서 범위 초과하여 0행으로 갔을때 N행에 놓아주고, 1열에서 범위를 초과하여 0열로 갔을 때 N열에 놓으면 됨

반대로, N행에 있다가 범위를 초과하여 N + 1행으로 가면, 다시 1행에 놓아주면 됨

 

[ 그림참고 ]

https://jennnn.tistory.com/77

 

1. 모든 파이어볼은 방향 d로 속력 s칸 만큼 이동함

2. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어남

  1) 같은 칸에 있는 파이어볼은 모두 하나로 합쳐짐

  2) 파이어볼은 4개의 파이어볼로 나누어짐

  3) 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같음

     a. 질량 =  (합쳐진 파이어볼의 질량의 합) / 5

     b. 속력 =  (합쳐진 파이어볼의 질량의 합) / (합쳐진 파이어볼의 개수)

           ㄴ 합쳐지는 파이어볼의 방향이 모두 홀수 or 짝수이면 방향은 0,2,4,6 ! 모두 홀짝 아니면 1,3,5,7

     c. 질량이 0인 파이어볼은 소멸되어 없어짐

 

3. 풀이

움직(move)이고, 중복된 것 나누기(overlap) 함수를 k번 반복하면 된다

0이면 소멸 !! ⭐️

 

- 3차원 벡터를 쓰는게 익숙치 않아서 좀 고민했다

- 모두 홀수 or 짝수 구하는 로직은 생각보다 간단하다

변수 odd, even을 false로 놓고 파이어볼마다의 방향에 따라 odd, even을 true로 바꿔주면

전체가 짝수라면, even만 true이고 odd는 여전히 false일 것이다.

반대로 홀수라면, odd만 true이고 even은 여전히 false일 것이다.

=> 1,3,5,7

 

4. 구현

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

#define MAX 60
int N, M, K, r, c, m, s, d, result = 0;
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
struct FireBall {
    int r, c, weight, speed, dir;
};
vector<FireBall> fireball;
vector<FireBall> map[MAX][MAX];

void move() { //파이어볼 이동시킨 후 map에 push
    for (auto &f: fireball) {
        int nx = dx[f.dir] * (f.speed % N) + f.r;
        int ny = dy[f.dir] * (f.speed % N) + f.c;

        while (nx < 1) {
            nx += N;
        }
        while (nx > N) {
            nx -= N;
        }
        while (ny < 1) {
            ny += N;
        }
        while (ny > N) {
            ny -= N;
        }

        map[nx][ny].push_back({nx, ny, f.weight, f.speed, f.dir});
    }
}

void overlap() { //겹치는 것 나누기 => 파이어볼이 됨
    vector<FireBall> tmp;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (map[i][j].size() == 1) {
                tmp.push_back({map[i][j][0]});
            } else if (map[i][j].size() > 1) { //나누기
                int weight = 0, speed = 0;
                bool even = false, odd = false, other = true;

                for (auto &z: map[i][j]) {
                    weight += z.weight;
                    speed += z.speed;
                }
                weight /= 5;
                speed /= (int) map[i][j].size();

                if(weight == 0) //소멸
                    continue;

                /* 방향 */
                for (auto &z: map[i][j]) {
                    if (z.dir % 2) //홀수
                        odd = true;
                    else {
                        even = true;
                    }
                }
                if (!odd && even) { //짝수일 때
                    other = false;
                } else if (!even && odd) { //홀수일 때
                    other = false;
                }
                if (!other) { //모두 짝수이거나 홀수일 때
                    tmp.push_back({i, j, weight, speed, 0});
                    tmp.push_back({i, j, weight, speed, 2});
                    tmp.push_back({i, j, weight, speed, 4});
                    tmp.push_back({i, j, weight, speed, 6});
                } else {
                    tmp.push_back({i, j, weight, speed, 1});
                    tmp.push_back({i, j, weight, speed, 3});
                    tmp.push_back({i, j, weight, speed, 5});
                    tmp.push_back({i, j, weight, speed, 7});
                }
            }
        }
    }
    fireball = tmp;
}

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

    cin >> N >> M >> K;
    while (M--) {
        cin >> r >> c >> m >> s >> d;
        fireball.push_back({r, c, m, s, d});
    }

    while (K--) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                map[i][j].clear();
            }
        }
        move(); //이동
        overlap(); //중복된 거 나누기
    }

    for (auto &f: fireball) {
        result += f.weight;
    }
    cout << result;
    return 0;
}