[BOJ] 20057 : 마법사 상어와 토네이도

문제 링크

20057번: 마법사 상어와 토네이도 (acmicpc.net)

20057번: 마법사 상어와 토네이도

저번에 풀었던 "마법사 상어와 파이어볼" 문제와 비슷한 유형의 문제인듯하다.

풀이

이번엔 마법사 상어가 토네이도를 배웠다. 토네이도는 격자의 중앙을 중심으로 반시계방향으로 커지면서 움직인다.

토네이도는 이동하면서 칸에 있는 모래를 분산시키는데 x -> y 로 왼쪽방향으로 이동하는 것을 예로 들었을 때, 왼쪽 그림과 같은 비율로 모래들이 분산된다.

알파는 각 비율만큼 모래가 날아간 후 남은 모래가 알파 만큼이다. 즉 y에 있는 모래는 전부 각 칸으로 분산되고 y에는 0의 모래가 남는다.

그리고 이동방향이 바뀌면 왼쪽 그림을 회전시켜서 똑같이 적용시키면 된다.

 

 

• 토네이도의 회전은 어떻게 표현할 것인가??

그림으로 주어진 토네이도의 진행을 보고 규칙을 찾아냈다. 일단 중심부를 기준으로 왼쪽방향으로 먼저 진행된다.

방향전환은 왼쪽, 아래쪽, 오른쪽, 위쪽 순서대로 순환한다.

그리고 이동 칸수를 보면 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ... 이렇게 진행되는 것을 알 수 있다.

즉 2턴이 지날때 마다 그 방향으로 이동하는 칸수가 1 늘어난다. 그리고 (1,1)에 도달하게 되면 토네이도는 종료된다.

• 모래의 분산은 어떻게 구현할 것인가???

모래의 분산에는 특별한 규칙이 없고 그냥 주어진 그림을 이용해야한다.

나는 그냥 노가다로 모래를 분산시켜주고 만약 분산시키려는 칸이 범위 밖이면 ans라는 변수에 값을 더해줬다.

그리고 알파 자리에는 기존의 모래에서 분산시키고 남은 모래를 주었다. 여기 주의할 점은 각 비율만큼 모래를 분산할 때 소수점 아래값은 다 버린다.

최종적으로 (1,1)까지 이동한 후 ans에 들어있는 값이 정답이 된다.

#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 = 500 + 5;
int N;
int A[MAX_N][MAX_N];
int ans;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
 
bool is_ok(pair<int, int>);
void go_left(pair<int,int>);
void go_right(pair<int, int>);
void go_down(pair<int, int>);
void go_up(pair<int, int>);
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
 
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> A[i][j];
 
    pair<int, int> now = { (N + 1) / 2, (N + 1) / 2 };
    int Direction = 0;
    for (int i = 1; i <= N; i++) {
        if (now.first == 1 && now.second == 1)
            break;
        for (int j = 1; j <= 2; j++) {
            for (int k = 1; k <= i; k++) {
                pair<int, int> next = { now.first + dy[Direction], now.second + dx[Direction]};
                if (Direction == 0)
                    go_left(next);
                else if (Direction == 1)
                    go_down(next);
                else if (Direction == 2)
                    go_right(next);
                else if (Direction == 3)
                    go_up(next);
                now = next;
            }
            Direction++;
            if (Direction == 4)
                Direction = 0;
        }
    }
    cout << ans << "\n";
    return 0;
}
 
bool is_ok(pair<int, int> now) {
    if (now.first < 1 || now.first > N || now.second < 1 || now.second > N)
        return false;
    return true;
}
 
void go_left(pair<int, int> now) {
    int Origin_Sand = A[now.first][now.second];
    int total = 0;
    pair<int,int> next = { now.first - 1, now.second + 1 };
    int Sand = Origin_Sand / 100;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first + 1, now.second + 1 };
    Sand = Origin_Sand / 100;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first - 1, now.second};
    Sand = Origin_Sand * 7 / 100;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first + 1, now.second};
    Sand = Origin_Sand * 7 / 100;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first - 1, now.second - 1 };
    Sand = Origin_Sand / 10;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first + 1, now.second - 1 };
    Sand = Origin_Sand / 10;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first + 2, now.second};
    Sand = Origin_Sand / 50;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first - 2, now.second };
    Sand = Origin_Sand / 50;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first, now.second - 2 };
    Sand = Origin_Sand / 20;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first, now.second - 1 };
    Sand = Origin_Sand - total;
    if (is_ok(next)) {
        A[next.first][next.second] += Sand;
    }
    else
        ans += Sand;
    A[now.first][now.second] = 0;
}
 
 
void go_right(pair<int, int> now) {
    int Origin_Sand = A[now.first][now.second];
    int total = 0;
 
    pair<int, int> next = { now.first - 1, now.second - 1 };
    int Sand = Origin_Sand / 100;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first + 1, now.second - 1 };
    Sand = Origin_Sand / 100;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first - 1, now.second };
    Sand = Origin_Sand * 7 / 100;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first + 1, now.second };
    Sand = Origin_Sand * 7 / 100;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first - 1, now.second + 1 };
    Sand = Origin_Sand / 10;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first + 1, now.second + 1 };
    Sand = Origin_Sand / 10;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first + 2, now.second };
    Sand = Origin_Sand / 50;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first - 2, now.second };
    Sand = Origin_Sand / 50;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first, now.second + 2 };
    Sand = Origin_Sand / 20;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first, now.second + 1 };
    Sand = Origin_Sand - total;
    if (is_ok(next)) {
        A[next.first][next.second] += Sand;
    }
    else
        ans += Sand;
    A[now.first][now.second] = 0;
}
 
 
void go_down(pair<int, int> now) {
    int Origin_Sand = A[now.first][now.second];
    int total = 0;
    pair<int, int> next = { now.first - 1, now.second + 1 };
    int Sand = Origin_Sand / 100;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first - 1, now.second - 1 };
    Sand = Origin_Sand / 100;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first, now.second + 1};
    Sand = Origin_Sand * 7 / 100;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first, now.second - 1 };
    Sand = Origin_Sand * 7 / 100;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first + 1, now.second - 1 };
    Sand = Origin_Sand / 10;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first + 1, now.second + 1 };
    Sand = Origin_Sand / 10;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first, now.second - 2 };
    Sand = Origin_Sand / 50;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first, now.second + 2};
    Sand = Origin_Sand / 50;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first + 2, now.second};
    Sand = Origin_Sand / 20;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first + 1, now.second};
    Sand = Origin_Sand - total;
    if (is_ok(next)) {
        A[next.first][next.second] += Sand;
    }
    else
        ans += Sand;
    A[now.first][now.second] = 0;
}
 
void go_up(pair<int, int> now) {
    int Origin_Sand = A[now.first][now.second];
    int total = 0;
 
    pair<int, int> next = { now.first + 1, now.second + 1 };
    int Sand = Origin_Sand / 100;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first + 1, now.second - 1 };
    Sand = Origin_Sand / 100;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first, now.second + 1 };
    Sand = Origin_Sand * 7 / 100;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first, now.second - 1 };
    Sand = Origin_Sand * 7 / 100;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first - 1, now.second - 1 };
    Sand = Origin_Sand / 10;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first - 1, now.second + 1 };
    Sand = Origin_Sand / 10;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first, now.second - 2 };
    Sand = Origin_Sand / 50;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first, now.second + 2 };
    Sand = Origin_Sand / 50;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first - 2, now.second };
    Sand = Origin_Sand / 20;
    if (is_ok(next)) {
        total += Sand;
        A[next.first][next.second] += Sand;
    }
    else {
        ans += Sand;
        total += Sand;
    }
 
    next = { now.first - 1, now.second };
    Sand = Origin_Sand - total;
    if (is_ok(next)) {
        A[next.first][next.second] += Sand;
    }
    else
        ans += Sand;
    A[now.first][now.second] = 0;
}