[백준/C++] 21610번 마법사 상어와 비바라기

백준

 

---

🤔문제 이해

그냥 단순 구현 문제로 잘 읽고 조건에 맞춰 비구름을 옮겨주면 되는 문제였다. 

---

🔥풀이🔥

(i, j)에 위치한 바구니에 담긴 물의 양을 나타내는 배열 map[i][j]

명령 과정 3번에서 사라진 구름을 표시하는 배열 visited[i][j]

명령에서 주는 방향을 의미하는 di[k]와 dj[k]

거리가 1인 대각선을 의미하는 diag_i[k]와 diag_j[k]

구름의 위치를 저장할 큐 cloud

 

m번의 명령마다 아래 과정을 수행해준다.

1. cloud의 front 비구름의 위치에 방향 * 거리값을 더해주고 격자크기(N)만큼 나머지 연산

2. 계산된 위치값이 음수이거나 0이면 +N

3. pop해주고 계산된 위치값의 비의 양을 +1하고 위치값을 cloud에 push

4. 옮겨진 비구름에 대해 대각선 거리1에 물이 있는 바구니의 개수만큼 비구름이 위치한 바구니에 물 추가

5. 문제의 명령 과정 3번에서 사라진 구름임을 visited에 표시

6. 모든 바구니를 돌면서 명령 과정 3번에서 사라진 구름이 아니면서 바구니에 물이 2이상 있는 곳의 위치를 cloud에 추가하고 바구니에서 물 2 뺌

7. visited 초기화

 

마지막엔 map의 모든 값을 다 더해 출력해준다.

---

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int n, m, r, c, d, s;
int map[51][51];
bool visited[51][51];
int di[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
int dj[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
int diag_i[4] = {-1, -1, 1, 1};
int diag_j[4] = {-1, 1, -1, 1};
queue<pair<int, int>> cloud;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
        }
    }

    cloud.push({n, 1});
    cloud.push({n, 2});
    cloud.push({n - 1, 1});
    cloud.push({n - 1, 2});

    for (int i = 0; i < m; i++) {
        cin >> d >> s;
        int size = cloud.size();
        for (int j = 0; j < size; j++) {
            r = (cloud.front().first + di[d] * s) % n;
            c = (cloud.front().second + dj[d] * s) % n;
            if (r <= 0) {
                r += n;
            }
            if (c <= 0) {
                c += n;
            }
            cloud.pop();
            cloud.push({r, c});
            map[r][c]++;
        }
        while (!cloud.empty()) {
            int cnt = 0;
            r = cloud.front().first;
            c = cloud.front().second;
            cloud.pop();
            for (int k = 0; k < 4; k++) {
                int mr = r + diag_i[k];
                int mc = c + diag_j[k];
                if (mr <= 0 || mc <= 0 || mr > n || mc > n) continue;
                if (map[mr][mc] > 0)
                    cnt++;
            }
            visited[r][c] = true;
            map[r][c] += cnt;
        }
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (map[j][k] >= 2 && !visited[j][k]) {
                    cloud.push({j, k});
                    map[j][k] -= 2;
                }
            }
        }
        memset(visited, false, sizeof(visited));
    }
    int total = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            total += map[i][j];
        }
    }
    cout << total;
}