[BOJ] 21610 : 마법사 상어와 비바라기

문제 링크

https://www.acmicpc.net/problem/21610

21610번: 마법사 상어와 비바라기

마법사 상어 시리즈 中 비바라기 편

골드5티어로 나와있는데 왜이렇게 헤맸는지 모르겠다.

풀이

마법사 상어는 비바라기 스킬을 배우게 됐다.

N x N 격자판에서 비바라기 스킬을 연습중이다. 비바라기를 시전하면 초기에  (N, 1), (N, 2), (N-1, 1), (N-1, 2) 좌표에 비구름이 4개 생긴다.

상어는 M번 동안 비구름에 명령을 내릴 수 있고, 이동방향은 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.

1. 모든 구름이 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)뿐이다.
5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

다음과 같이 상어가 명령을 내린 후의 비바라기 진행을 명시 해두었다.

위와 같은 과정을 거치기 위해 우리는 어떤 정보를 저장하고 변경해야할까?

  1. 모든 구름의 위치에 대한 정보

구름의 위치에 대한 정보를 알아야 구름을 이동시키고 구름이 있는 위치에 비를 내려줄 수 있다.

구름에 대한 정보는 Clouds 라는 벡터에 구름의 좌표를 저장하는 것으로 했다.

  2. 제일 최근에 구름이 어디에 존재했는지

5번 명령에서 물의 양이 2이상인 모든 칸에 구름이 생기는데, 구름이 사라졌던 칸에서는 구름이 생기지 않는다.

따라서 최근에 어디서 구름이 사라졌는지에 대한 정보가 필요하다.

나는 visited[50][50] 배열을 선언해서 구름이 있었던 자리만 true로 표시해주었다.

표시하는 시점은 구름을 이동시킬 때 이동 후의 자리를 표시해주면 된다.

  3. 각 격자가 가지고있는 물의 양에 대한 정보

각 격자 칸마다 물의 양을 과정이 진행됨에 따라 계속 변경해주어야한다. 문제에서 주어진대로 A[r][c] 배열을 만들어서 각 칸마다 물의 양을 저장했다.

우리가 가지고 있으면서 수정해야 할 정보는 크게 위의 3가지로 정리할 수 있다.

 

• 구름의 이동

상어가 명령을 내리면 구름은 d 방향으로 s만큼 이동한다.

이때 격자판은 1번 행,열과 N번 행,열이 연결되어 있기때문에 범위를 벗어나는 경우는 없다.

구름이 어떤 방향으로 N칸 이동할 경우 결국 제자리도 돌아온다. 그렇기 때문에 S가 N보다 큰 경우

S %= N 의 과정을 통해 이동거리를 줄일 수 있다.

 pair<int, int> now = Clouds[i];
 now.first = now.first + dy[direction] * speed + N;
 now.second = now.second + dx[direction] * speed + N;
 if (now.first > N)
 	now.first %= N;
 if (now.second > N)
 	now.second %= N;
 if (now.first == 0)
 	now.first += N;
 if (now.second == 0)
    now.second += N;​

나는 구름의 이동을 위와 같이 구현하였다.

만약 방향이 - 방향인 경우, 방향 * s 만큼 이동 하면 좌표가 음수가 될 수 있다.

그렇기 때문에 항상 + N 을 해주면 음수인 경우가 없어진다.

대신 %N을 했을 때 0이 되는 경우가 있는데 0은 1에서 -방향으로 1칸 이동한 것이기 때문에 사실 N번 칸이다.

그렇기 때문에 행 또는 열이 0인 경우에는 N으로 바꿔준다.

#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;
int dx[] = { 0,-1,-1,0,1,1,1,0,-1 };
int dy[] = { 0,0,-1,-1,-1,0,1,1,1 };
int A[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
vector<pair<int, int>> Clouds;
 
void Move_Cloud(int direction, int speed);
bool is_ok(pair<int, int> Position);
void Rain();
void Bug();
void Make_Cloud();
int get_water();
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> A[i][j];
    //초기 구름 생성
    Clouds.push_back({ N,1 });
    Clouds.push_back({ N,2 });
    Clouds.push_back({ N - 1,1 });
    Clouds.push_back({ N - 1,2 });
    for (int i = 1; i <= M; i++) {
        int d, s;
        cin >> d >> s;
        Move_Cloud(d, s);
        Rain();
        Bug();
        Make_Cloud();
    }
    cout << get_water() << "\n";
    return 0;
}
 
void Move_Cloud(int direction, int speed) {
    speed %= N;
    memset(visited, false, sizeof(visited));
    for (int i = 0; i < Clouds.size(); i++) {
        pair<int, int> now = Clouds[i];
        now.first = now.first + dy[direction] * speed + N;
        now.second = now.second + dx[direction] * speed + N;
        if (now.first > N)
            now.first %= N;
        if (now.second > N)
            now.second %= N;
        if (now.first == 0)
            now.first += N;
        if (now.second == 0)
            now.second += N;
        Clouds[i] = now;
        visited[now.first][now.second] = true;
    }
}
 
void Rain() {
    for (int i = 0; i < Clouds.size(); i++)
        A[Clouds[i].first][Clouds[i].second]++;
}
 
 
bool is_ok(pair<int, int> Position) {
    if (Position.first < 1 || Position.first > N || Position.second < 1 || Position.second > N)
        return false;
    return true;
}
 
void Bug() {
    for (int i = 0; i < Clouds.size(); i++) {
        pair<int, int> now = Clouds[i];
        int cnt = 0;
        for (int j = 2; j <= 8; j += 2) {
            pair<int, int> next = { now.first + dy[j], now.second + dx[j] };
            if (is_ok(next) && A[next.first][next.second] >= 1)
                cnt++;
        }
        A[now.first][now.second] += cnt;
    }
}
 
 
void Make_Cloud() {
    Clouds.clear();
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (A[i][j] >= 2 && !visited[i][j]) {
                Clouds.push_back({ i,j });
                A[i][j] -= 2;
            }
        }
    }
    memset(visited, false, sizeof(visited));
}
 
int get_water() {
    int ret = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            ret += A[i][j];
    return ret;
}

기존의 내 코드가 뭐가 잘못됐는지는 모르겠지만, 구름을 이동시키는 과정에서 뭔가 문제가 있었던 것같다. 예제문제는 다 잘 출력돼서 어디서 틀렸는지 찾기가 더 어려웠다.