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

마법사 상어와 파이어볼 문제 링크

[내 풀이]
이러한 구현 문제를 풀 때는 조건을 잘 기억해서 빠짐없이 다 포함해서 푸는 것이 중요한 것 같다.
여기서 신경써야 하는 것은

1) 1번 행이 N번 행과 연결되어 있고, 1번 열을 N번 열과 연결되어 있다는 점
2) 이동하는 중에는 같은 칸에 여러 파이어볼이 존재한다는 점
3) 합쳐지는 파이어볼의 방향이 모두 홀수 혹은 모두 짝수이면 방향을 0,2,4,6,
그렇지 않으면 1,3,5,7이라는 점
4) 질량이 0인 파이어볼은 소멸된다는 점이다

그리고 자료구조를 어떻게 담을지가 관건인데 나는 파이어볼 당 질량, 속도, 방향 정보가 있다는 것과 같은 같에 여러 파이어볼이 존재한다는 점 때문에 벡터 이차원 배열을 선언했다. 2,3,4 번은 trivial한 것이라서 빼먹지 않고 구현하면 되는 것인데 1번은 조금 생소했다.

위와 같이 N이 4이고 index 0에 파이어볼이 있을 때, 속력이 10이라고 하자. 저 파이어 볼이 현재 있는 위치로 돌아오기 위해서는 속력이 N의 배수여야 한다. 즉, 속력/N번 원래 자리로 돌아간 후 속력%N만큼 이동한다.속력이 10임으로 10%4 == 2라서 index 2로 가게 된다. 원래 있던 자리에서 이동한 만큼이 N을 넘을 때가 있는데 그럴시 N을 빼주면 해결된다.
방향이 반대인 경우가 있는데 위와 동일한 procedure인데 방향이 반대인 만큼 0보다 작아지는 경우가 있다. 그럴시 N을 더해 주면 된다.

[내 코드]

#include <iostream>
#include <vector>
#define N_MAX 51

using namespace std;

int N, M, K;
struct info {
    int m;  //질량
    int s;  //속력
    int d;  //방향

    info(int _m, int _s, int _d) :m(_m), s(_s), d(_d) {};
};
vector<info> map[N_MAX][N_MAX];
int dir_y[8] = { -1,-1,0,1,1,1,0,-1 };
int dir_x[8] = { 0,1,1,1,0,-1,-1,-1 };


int calc_mass() {
    int result = 0;
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++) {
            if (map[y][x].empty()) continue;
            for (int i = 0; i < map[y][x].size(); i++) {
                result += map[y][x][i].m;
            }
        }
    }
    return result;
}


void follow_order() {
    vector<info> c_map[N_MAX][N_MAX]; //움직인 파이어볼 저장하는 곳
    //파이오볼 움직이기
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++) {
            if (map[y][x].empty()) continue;
            while (!map[y][x].empty()) {
                info cur = map[y][x].back();
                map[y][x].pop_back();

                int real_s = cur.s % N;
                int new_y = y + dir_y[cur.d] * real_s;
                int new_x = x + dir_x[cur.d] * real_s;

                if (new_y < 0) new_y += N;
                else if (new_y >= N) new_y -= N;

                if (new_x < 0) new_x += N;
                else if (new_x >= N) new_x -= N;


                c_map[new_y][new_x].push_back(cur);
            }
        }
    }

    //한 칸에 파이어볼 2개 이상일시 파이어볼 나눠지기
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++) {
            map[y][x].clear();
            if (c_map[y][x].empty()) continue;
            if (c_map[y][x].size() == 1) {
                map[y][x] = c_map[y][x]; //원래 맵으로 다시 옮기기
            }
            else {
                //2개 이상이라서 합쳐지고 나눠짐
                int summed_m = 0, summed_s = 0;
                int size_ball = c_map[y][x].size();
                bool flag_h = false, flag_o = false;
                while (!c_map[y][x].empty()) {
                    info cur = c_map[y][x].back();
                    c_map[y][x].pop_back();
                    summed_m += cur.m;
                    summed_s += cur.s;
                    if (cur.d % 2) flag_h = true;
                    else flag_o = true;
                }
                summed_m = summed_m / 5;
                summed_s = summed_s / size_ball;
                if (summed_m == 0) continue;
                vector<int> summed_dir;
                if (flag_h && flag_o) summed_dir = { 1,3,5,7 };
                else summed_dir = { 0,2,4,6 };
                for (int j = 0; j < 4; j++) {
                    map[y][x].push_back(info(summed_m, summed_s, summed_dir[j]));
                }
            }
        }
    }

}

int solve() {
    for (int k = 0; k < K; k++) {
        follow_order();
    }
    return calc_mass();
}

int main() {
    cin >> N >> M >> K;
    int y, x, m, s, d;
    for (int order = 0; order < M; order++) {
        cin >> y >> x >> m >> s >> d;
        map[y - 1][x - 1].push_back(info(m, s, d));
    }
    int ans = solve();
    cout << ans << "\n";
}

[총평]
맵이 연결되어 있다는 곳에서 로직을 지엽적으로 짜서 오래 걸렸다...