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

문제 링크

20056번: 마법사 상어와 파이어볼 (acmicpc.net)

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

마법사가 된 상어가 파이어볼에 내린 명령을 구현하는 문제.

이전에 풀었던 아기상어 문제의 연관 문제인 것같다.

풀이

파이어볼은 크기가 N x N인 격자에서 움직이며 1번 행과 열은 각각 N번 행과 열과 연결되어있다. 즉 파이어볼이 격자 밖으로 나가는 일은 없다.

모든 파이어볼은 명령 1번당 1회씩 이동한다. 그리고 이동 후 한 칸에 여러개의 파이어볼이 있으면 합쳐졌다가 4개의 파이어볼로 분할된다.

내가 저장해야할 정보는

①. 파이어볼들에 대한 정보

②. 각 칸에 어느 파이어볼이 들어있는지에 대한 정보

=> 각 칸에 들어있는 파이어볼의 인덱스를 저장해두었다.

만약 임의의 칸에 들어있는 파이어볼이 2개이상이면 이 칸에 있는 파이어볼은 분할되어야한다.

①. 파이어볼들에 대한 정보는 나는 vector<pair<pair<int, int>, pair<int, pair<int, int>>>> Fireball; 이렇게

②. 각 칸에 들어있는 파이어볼에 대한 정보는 

vector<int> Map[MAX_N][MAX_N] 이렇게 Map이라는 벡터 2차원배열을 선언해서 정보를 저장했다.

 

 1. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.

여기서 Si가 격자의 크기인 N보다 크다고 생각해보자. 만약 크기가 6인 격자에서 x축방향으로 6만큼 이동하면 제자리로 돌아오게 된다. 제자리로 돌아오는 만큼의 이동은 굳이 구현해줄 필요가 없다. 그렇기 때문에 Si % N만큼 이동해주면 된다.

여기서 파이어볼을 이동시켰을 때 행이나 열이 1보다 작아지거나 N보다 커지는 경우를 잘 생각해서 파이어볼들을 이동시켜 준다.

그리고 이동 후의 위치를 ( r , c ) 라고 한다면 Map[r][c] 에 이동시킨 파이어볼의 인덱스를 넣어준다.

 

2. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 분할이 일어난다.

분할 후 ①. 파이어볼들에 대한 정보가 변경될 것이다. 기존의 파이어볼은 없어지고 새로운 파이어볼만 남아있어야한다.그래서 나는 temp라는 벡터에 분할 후에 있어야 하는 파이어볼들의 정보를 저장해두었다.

Map배열의 인덱스를 돌면서 해당 칸의 벡터 크기가 0이면 즉 파이어볼이 0개 있으면 스킵.

해당 칸 벡터 크기가 1이면 파이어볼이 1개 있다는 뜻이므로 분할할 필요 X. 그리고 분할 후에도 그대로 남아있어야함

=> temp 배열에 해당 파이어볼 정보 저장

해당 칸의 벡터 크기가 2이상이면 파이어볼들을 합친 후 분할시켜야한다.

새로 만들어질 4개의 파이어볼들에 대한 정보만 temp에 저장해준다.

=> 기존의 파이어볼은 사라지기 때문.

이렇게 해서 마지막에 Fireball = temp 를 통해 파이어볼들에 대한 정보를 변경시킨다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <deque>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 50 + 5;
int N, M, K;
int dx[] = { 0,1,1,1,0,-1,-1,-1 };
int dy[] = { -1,-1,0,1,1,1,0,-1 };
vector<pair<pair<int, int>, pair<int, pair<int, int>>>> Fireball;
vector<pair<pair<int, int>, pair<int, pair<int, int>>>> temp;
vector<int> Map[MAX_N][MAX_N];
 
void move_and_seperate();
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M >> K;
    for (int i = 0; i < M; i++) {
        int r, c, m, d, s;
        cin >> r >> c >> m >> s >> d;
        Fireball.push_back({ {r,c},{m,{d,s}} });
    }
    while (K--) {
        move_and_seperate();
    }
    int ans = 0;
    for (int i = 0; i < Fireball.size(); i++) {
        ans += Fireball[i].second.first;
    }
    cout << ans << "\n";
    return 0;
}
 
void move_and_seperate() {
    //Move
    for (int i = 0; i < Fireball.size(); i++) {
        pair<int, int> now = Fireball[i].first;
        int mass = Fireball[i].second.first;
        int direct = Fireball[i].second.second.first;
        int speed = Fireball[i].second.second.second;
        int move = speed % N;
        pair<int, int> next = { now.first + dy[direct] * move, now.second + dx[direct] * move };
        if (next.first < 1) {
            next.first %= N;
            next.first += N;
        }
        else if (next.first > N)
            next.first %= N;
 
        if (next.second < 1) {
            next.second %= N;
            next.second += N;
        }
        else if (next.second > N)
            next.second %= N;
 
        Fireball[i].first = next;
        Map[next.first][next.second].push_back(i);
    }
    //Seperate
    temp.clear();
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (Map[i][j].empty())
                continue;
            else if (Map[i][j].size() == 1) {
                temp.push_back(Fireball[Map[i][j][0]]);
                Map[i][j].clear();
                continue;
            }
            int Mass_total = 0;
            int Speed_total = 0;
            int odd = 0;
            for (int k = 0; k < Map[i][j].size(); k++) {
                Mass_total += Fireball[Map[i][j][k]].second.first;
                Speed_total += Fireball[Map[i][j][k]].second.second.second;
                if (Fireball[Map[i][j][k]].second.second.first % 2)
                    odd++;
            }
            Mass_total = (int)floor((double)Mass_total / 5);
            if (Mass_total == 0) {
                Map[i][j].clear();
                continue;
            }
            Speed_total = (int)floor((double)Speed_total / Map[i][j].size());
            int Direction[] = { 0,2,4,6 };
            if (odd != 0 && odd != Map[i][j].size())
                for (int i = 0; i < 4; i++)
                    Direction[i] ++;
            for (int k = 0; k < 4; k++)
                temp.push_back({ {i,j},{Mass_total,{Direction[k], Speed_total}} });
            Map[i][j].clear();
        }
    }
    Fireball = temp;
}

하고 나니까 사실 별거 아닌거같은데, 내 기준으로 구현이 조금 까다롭고 오래걸렸다.