[백준 21610 마법사 상어와 비바라기]

A. 접근법

차근 차근 문제의 요구에 따라 구현하면 되는 '시뮬레이션'문제이다.

구름이 있는 칸은 M으로 표시하여 M번의 이동 중 생긴 구름이라고 구분해준다.

B. 구현

1. 모든 구름이 di 방향으로 si칸 이동한다.

   구름뿐만 아니라 구름이 없는 칸도 di방향으로 si칸 이동한다로 구현하면 편하다.

2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
3. 구름이 모두 사라진다.
4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.

• 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
• 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.

  동시에 물복사버그가 수행된다. 수행되기 전의 배열을 복사하고 이것을 기준으로 물복사버그를 수행한다. 복사하지 않고 진행할 경우 물복사버그로 인하여 0이었던 칸이 물이 생겼을 때, 이 칸이 다른 칸의 물복사버그할 때 영향을 줄 가능성이 있다.

5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

C. 코드

#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> table;
vector<vector<int>> mv;
vector<vector<int>> cloud;
int T, N, M;

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

int chk(int x, int y) {
    if(x < 0 || x >= N || y < 0 || y >= N)
        return 0;
    else {
        if(table[x][y] > 0)
            return 1;
        else
            return 0;
    }
}
void solver(int stg, int di, int si) {

    vector<vector<int>> tCloud(cloud);
    for(int i = 0; i < cloud.size(); i++) {
        for(int j = 0; j < cloud[i].size(); j++) {

            if(1) {
                int nx, ny;
                nx = i + (dx[di] * si);
                ny = j + (dy[di] * si);

                //cout << dx[di] << " , " << si;
                while( nx < 0 || nx >= N || ny < 0 || ny >= N) {
                    if(nx < 0)
                        nx += N;
                    if(ny < 0)
                        ny += N;
                    if(nx >= N)
                        nx -= N;
                    if(ny >= N)
                        ny -= N;
                }

                //cout << " -> " << nx << " , " << ny << endl;
                tCloud[nx][ny] = cloud[i][j];
            }
        }
    }

    cloud = tCloud;

    //cout << " Stage 2" << endl;
    //2
    for(int i = 0; i < cloud.size(); i++) {
        for(int j = 0; j < cloud[i].size(); j++) {
            if(cloud[i][j] == stg)
                table[i][j]++;
        }
    }

    // skip 3
    // 4
    vector<vector<int>> table2(table);
    for(int i = 0; i < cloud.size(); i++) {
        for(int j = 0; j < cloud[i].size(); j++) {
            if(cloud[i][j] == stg) {
                table2[i][j] += chk(i - 1, j - 1) + chk(i - 1, j + 1) + chk(i + 1, j - 1) + chk(i + 1, j + 1);
            }
        }
    }

    table = table2;

    vector<vector<int>> tCloud2(cloud);
    // 3 & 5
    for(int i = 0; i < cloud.size(); i++) {
        for(int j = 0; j < cloud[i].size(); j++) {
            if(cloud[i][j] == stg) {
                tCloud2[i][j] = 0;
            }

            else {
                if(table[i][j] >= 2) {
                    table[i][j] -= 2;
                    tCloud2[i][j] = stg + 1;
                }
            }
        }
    }

    cloud = tCloud2;
}
int main() {

    //scanf("%d", &T);

    T = 1;
    for(int tc = 0; tc < T; tc++) {
        scanf("%d %d", &N, &M);

        table.clear();
        cloud.clear();
        mv.clear();

        int tmp, tmp2;

        for(int i = 0; i < N; i++) {
            vector<int> tv(N, 0);
            cloud.push_back(tv);
            for(int j = 0; j < N; j++) {
                scanf("%d", &tmp);
                tv[j] = tmp;
            }
            table.push_back(tv);
        }
        for(int i = 0; i < M; i++) {
            vector<int> tv2(2, 0);
            scanf("%d %d", &tmp, &tmp2);
            tv2[0] = tmp;
            tv2[1] = tmp2;
            //cout << tmp2 << "!" << endl;
            mv.push_back(tv2);
        }
        cloud[N - 2][0] = 1;
        cloud[N - 1][0] = 1;
        cloud[N - 2][1] = 1;
        cloud[N - 1][1] = 1;


        for(int i = 0; i < M; i++) {
            solver(i + 1, mv[i][0] - 1, mv[i][1]);
        }
        int answer = 0;
        for(auto it = table.begin(); it != table.end(); it++) {
            for(auto it2 = it->begin(); it2 != it->end(); it2++) {
                //cout << *it2<< " ";
                answer += *it2;
            }//cout << endl;
        }

        printf("%d\n", answer);



    }

    return 0;
}

D. 결과