마법사 상어와 파이어볼

작성일 | In

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

문제 링크

시뮬레이션 문제이나 문제를 이해하는게 조금 어려웠다.
이해하기 어려웠던 문장인 “격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.” 라는 말은 파이어볼이 맵을 벗어나는 경우 없이 순환한다는 뜻이다. 만약 파이어볼이 현재 y=0에 위치해있고, 위로 한 칸 움직인다면 y=n-1에 위치하게 된다.

구현의 편의를 위해 파이어볼의 정보인 r,c,m,s,d를 FIREBALL 구조체를 만들어서 다루었고, 맵의 각 칸에 여러 개의 파이어볼이 위치할 수 있기 때문에 각 칸을 vector로 선언했다.
각 파이어볼을 움직일 때, 맵을 순차적으로 탐색하며 각 벡터에 저장되어있는 파이어볼을 움직이게 구현했다. 이 과정에서 변경사항을 바로 맵에 적용해 버리면, 파이어볼의 움직임에 따라 어떤 파이어볼은 두 번 이상 움직이게 될 수도 있으므로 변경사항은 queue에 임시로 저장해 두고, 모든 파이어볼을 움직인 뒤 queue의 내용을 맵에 반영했다.
파이어볼을 움직일 때는 시간 절약을 위해 한 칸 한 칸 움직이지 않고, 해당 파이어볼의 s(속력)을 곱한 값을 한 번에 더한 뒤 맵을 순회한다는 조건을 적용하기 위해 n으로 나머지 연산을 수행했다.
마지막으로 맵을 한 번 더 전체 순회하면서 해당 칸(vector)에 담겨있는 파이어볼의 개수가 2개 이상일 땐 문제 조건에 따라 이를 4개로 만들고, 해당 vector에 다시 삽입했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;

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

typedef struct fireball {
    int r,c,m,s,d;
}FIREBALL;

vector<FIREBALL> field[50][50];
int n,m,k;

void order() {
    while(k--) {
        queue<FIREBALL> que;
        for(int i=0; i<n; ++i) {
            for(int j=0; j<n; ++j) {
                while(!field[i][j].empty()) {
                    FIREBALL cur = field[i][j].back();
                    field[i][j].pop_back();

                    // 파이어볼 이동
                    // 맵은 순환 구조이므로 r,c가 0이상 n미만의 범위를 유지하도록 조정한다.
                    cur.r += (dy[cur.d] * cur.s) % n;
                    cur.c += (dx[cur.d] * cur.s) % n;

                    if(cur.r < 0)
                        cur.r += n;
                    if(cur.r >= n)
                        cur.r -= n;
                    if(cur.c < 0)
                        cur.c += n;
                    if(cur.c >= n)
                        cur.c -= n;

                    que.push(cur);
                }
            }
        }

        while(!que.empty()) {
            FIREBALL temp = que.front();
            que.pop();
            field[temp.r][temp.c].push_back(temp);
        }

        for(int i=0; i<n; ++i) {
            for(int j=0; j<n; ++j) {
                int vsize = field[i][j].size();
                if(vsize >= 2) {
                    int msum = 0, ssum = 0;
                    vector<int> ds;
                    while(!field[i][j].empty()) {
                        FIREBALL back = field[i][j].back();
                        field[i][j].pop_back();
                        msum += back.m;
                        ssum += back.s;
                        ds.push_back(back.d);
                    }

                    // 합쳐진 파이어볼의 방향 통일성 검사
                    int isSameD = field[i][j][0].d % 2 == 0 ? 0 : 1;
                    for(int k=0; k<vsize; ++k) {
                        if(isSameD == 1 && ds[k] % 2 == 0)
                            isSameD = -1;
                        else if(isSameD == 0 && ds[k] % 2 == 1)
                            isSameD = -1;
                    }

                    int nm = msum / 5;
                    int ns = ssum / vsize;
                    if(nm == 0)
                        continue;
                    for(int k=0; k<4; ++k)
                        field[i][j].push_back({i, j, nm, ns, isSameD == -1 ? k*2+1 : k*2});
                }
            }
        }
    }
}

int main(void) {
    scanf("%d %d %d", &n, &m, &k);

    for(int i=0; i<m; ++i) {
        int r, c, mm, s, d;
        scanf("%d %d %d %d %d", &r, &c, &mm, &s, &d);
        FIREBALL fireball = {r-1,c-1,mm,s,d};
        field[r-1][c-1].push_back(fireball);
    }

    order();

    int ans=0;
    for(int i=0; i<n; ++i) {
        for(int j=0; j<n; ++j) {
            for(int k=0; k<field[i][j].size(); ++k)
                ans += field[i][j][k].m;
        }
    }

    printf("%d", ans);
}
0%