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

문제 링크

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

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

2020년 하반기 새로운 상어 시리즈가 등장했습니다...! 마법까지 쓰게 될 줄이야...

 

---

모든 시뮬레이션 문제가 그렇지만 정말 위의 내용을 착실하게 구현하면 됩니다.

다른 상어 시리즈에 비해서 구현 난이도가 어렵지 않았습니다.

 

현재 위치(x,y), 질량(m), 방향(d), 속력(s)을 속성으로 갖는 파이어볼 구조체를 정의합니다.

 

 

파이어볼은 두 개 이상 충돌할 시 네 개의 파이어볼이 새롭게 생성되기 때문에 생성과 삭제가 빈번합니다.

그래서 저는 맵에 존재하는 파이어볼의 관리를 위해 map 구조체를 사용하였습니다. 다만, 파이어볼에 대한 정렬이 필요 없기 때문에 unordered_map(이하 map)을 사용합니다.

id는 새로운 파이어볼 객체가 생성될 때마다 1만큼 증가한 새로운 id를 부여합니다. id는 전역으로 관리했습니다.

여기까지, 입력으로 주어진 초기 상태에 대해 구현했고 이제 시뮬레이션을 진행하면 됩니다.

 

 

각 명령마다 map에 담겨있는 모든 파이어볼을 순회하면서 다음 위치(nx, ny)를 결정합니다.

 

다음 위치는 현재 위치 + 현재 속력 * 현재 방향으로 결정됩니다. 문제에서 0행과 N-1행 (열도 마찬가지)은 연결된다고 했기 때문에 n으로 나머지 연산을 해주어야 하는데요. 다음 위치의 좌표가 음수일 수도 있기 때문에 이에 대한 처리는 충분한 크기의 n의 배수를 더해준 후 나머지 연산을 처리하는 것으로 간단히 처리할 수 있습니다.

저의 경우 n과 파이어볼의 속력을 곱하여 사용했습니다.

 

예를 들어, 크기가 5*5인 격자에서 다음 위치의 행이 -3이라면, (-3+5)%5, (-3+10)%5, (-3+20)%5 등으로 처리 할 수 있습니다. 따라서 fb.x + dx[fb.d] * fb.s 보다 큰 n의 배수라면 무엇이든 사용할 수 있습니다.

 

이렇게, 다음 위치(ny, nx)가 결정되면 next_pos[ny][nx]에 해당 파이어볼의 id값을 넣습니다.

만약, next_pos의 한 칸에 두 개 이상의 id가 있다면 충돌이 발생한 것이겠죠.

 

 

line51~line53에서, next_pos의 모든 칸을 순회하며 두 개 이상이라면 새로운 질량과 속력을 계산합니다.

 

dir_flag는 새로운 방향을 결정하기 위한 변수입니다. 충돌한 파이어볼의 방향이 모두 짝수이거나 모두 홀수인 경우 dir_flag는 0 또는 충돌한 파이어볼의 개수가 됩니다.

 

line55에서, 충돌한 파이어볼은 모두 소멸되는 것으로 생각할 수 있으므로 map에서 지워줍니다.

새롭게 생성된 파이어볼의 질량이 0이라면 소멸한다고 했으므로 line59에 대한 처리를 꼭 해주어야 합니다.

새로운 파이어볼의 위치, 질량, 속력, 방향이 결정되었으므로 구조체 객체를 새로 생성하여 map에 넣어 관리합니다.

 

이를 K번 시뮬레이션하고 map에 남아 있는 파이어볼의 질량을 모두 더해서 출력하면 됩니다.

---

주의할 점

• 격자의 양 끝은 서로 연결되어 있다.
• 파이어볼은 이동중에 충돌하지 않고 오직 같은 칸에 도착했을 때만 충돌한다.
• 질량이 0인 파이어볼은 소멸된다.
• 충돌로 생겨난 네 개의 파이어볼은 충돌이 발생한 칸에 같은 시각에 생성된다.

---

소스코드

 

#include <cstdio>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

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

typedef struct fireBall {
    int x, y, m, s, d;
} fireBall;

vector <int> next_pos[55][55];
unordered_map <int, fireBall> FBs;
int fb_id;

int main()
{
    int n, m, k;
    int x, y, mass, dir, speed;
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %d %d %d", &x, &y, &mass, &speed, &dir);
        fireBall fb = { x, y, mass, speed, dir };
        FBs[fb_id++] = fb;
    }

    while (k--) {
        vector <int> next_pos[55][55];

        for (auto it = FBs.begin(); it != FBs.end(); ++it) {
            int id = it->first;
            fireBall fb = it->second;

            int nx = (fb.x + dx[fb.d] * fb.s + n * fb.s) % n;
            int ny = (fb.y + dy[fb.d] * fb.s + n * fb.s) % n;
            FBs[id].x = nx;
            FBs[id].y = ny;
            next_pos[nx][ny].push_back(id);
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int sz = next_pos[i][j].size();
                int sum_mass = 0, sum_speed = 0, dir_flag = 0;
                if (sz <= 1) continue;

                for (auto id : next_pos[i][j]) {
                    sum_mass += FBs[id].m;
                    sum_speed += FBs[id].s;
                    dir_flag += (FBs[id].d % 2);

                    FBs.erase(id);
                }

                int new_mass = sum_mass / 5;
                if (new_mass == 0) continue;

                int new_speed = sum_speed / sz;
                
                int k = (dir_flag == 0 || dir_flag == sz) ? 0 : 1;
                for (; k < 8; k += 2) {
                    fireBall fb = { i, j, new_mass, new_speed, k };
                    FBs[fb_id++] = fb;
                }
            }
        }
    }

    int ans = 0;
    for (auto it = FBs.begin(); it != FBs.end(); ++it) {
        ans += it->second.m;
    }

    printf("%d\n", ans);
    return 0;
}

 

 

 

 

 

공부한 것을 정리하기 위한 기록입니다.

틀린 부분이 있다면 부드럽게 알려주세요.