[백준 20057] 마법사 상어와 토네이도(C++)

📕문제

---

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A [r][c]는 (r, c)에 있는 모래의 양을 의미한다.

토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.

토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.

토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.

토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.

📕입력

---

첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A [r][c]이다.

📕출력

---

격자의 밖으로 나간 모래의 양을 출력한다.

📕제한

---

• 3 ≤ N ≤ 499
• N은 홀수
• 0 ≤ A[r][c] ≤ 1,000
• 가운데 칸에 있는 모래의 양은 0

🔎문제 해석

---

문제에서 중요한 부분인 방향 전환은 방향이 2번 바뀔 때마다 거리가 1씩 증가하는 사실을 알 수 있다.

우선 시작점은 행렬의 가운데라는 것은 모르면 안 된다.

방향은 왼쪽, 아래, 오른쪽, 위 이렇게 방향 배열을 만들었다. --> 시계방향

만약 a->b로 이동한다면 a에 있는 모래를 b로 옮기고 b에 있는 모래를 특별한 규칙에 따라 배분하고, 배분하고 남은 모래의 양은 c라는 지역으로 옮긴다. [만약 c에 모래가 있다면 c에 있는 기존의 모래의 양과 더해주면 된다.]

항상 계산은 소수점을 버리고 계산한다.

 

💡이제 모래를 배분하는데 두 가지 경우가 있다.

• 배분하는 지역이 행렬을 벗어난 경우
• 배분하는 지역이 행렬 내부인 경우

 

만약 행렬 내부인 경우 그 지역에서 배분하는 모래의 양을 더해주면 되지만,

배분하는 지역이 행렬을 벗어난 경우에는 외부로 빠져나간다고 계산해주고, 따로 더해줘야 한다. [문제에서 요구하는 값임]

방향의 값이 홀수이면 dist를 1씩 증가시킨다. [방향이 2번 바뀌면 거리가 1씩 증가한다. 그림을 자세히 보면 알 수 있음.]

그리고 현재 내가 dist만큼 갔다면 방향을 전환해준다.

방향은 계속 1씩 더해주지만 0,1,2,3이 반복되므로 4를 나눈 나머지를 넣어준다.

💻코드

/*
백준 골드4 20057 마법사 상어와 토네이도
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<vector<int>> g;
vector<int> x{0, 1, 0, -1};
vector<int> y{-1, 0, 1, 0};
vector<double> z{0.01, 0.07, 0.1, 0.02, 0.05};
int out = 0, step = 0, dist = 1;
void location(int a, int b, int temp, int k);
int main()
{
    cin >> n;
    g.resize(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> g[i][j];
        }
    }
    int nowR = n / 2, nowC = n / 2, afterR, afterC, move = 0;
    bool check = true;
    while (check)
    {                                 // 1,1까지 이동한 뒤 소멸해야함.
        int csand = g[nowR][nowC];    //현재 좌표에서 모래
        afterR = nowR + x[move];      //이동한 x좌표.
        afterC = nowC + y[move];      //이동한 y좌표
        int temp = g[afterR][afterC]; //이동한 자리에 있던 모래
        g[afterR][afterC] = csand; //이동한 자리에 있던 모래를 기존의 모래로 채운다.
        int sum = 0; //모래의 양
        if (move == 0)
        { //왼쪽으로 1칸
            step += 1;
            for (int k = 0; k < 3; k++)
            {
                location(nowR - 1, nowC - k, temp, k);
                location(nowR + 1, nowC - k, temp, k);
                sum += temp * z[k];
                sum += temp * z[k];
            }
            location(afterR + 2, afterC, temp, 3);
            location(afterR - 2, afterC, temp, 3);
            location(nowR + 3 * x[move], nowC + 3 * y[move], temp, 4); // a + 진행방향
            sum += temp * z[3];
            sum += temp * z[3];
            sum += temp * z[4];
            // sum에는 이제 다 분배된 모래가 들어있음. 이제 나머지는 알파에 넣어야함.
            if (afterR + x[move] < 0 || afterR + x[move] >= n || afterC + y[move] < 0 || afterC + y[move] >= n)
            {
                out += temp - sum;
            }
            else
                g[afterR + x[move]][afterC + y[move]] += temp - sum;
        }
        else if (move == 1)
        { //아래로 한칸
            step += 1;
            for (int k = 0; k < 3; k++)
            {
                location(nowR + k, nowC - 1, temp, k);
                location(nowR + k, nowC + 1, temp, k);
                sum += temp * z[k];
                sum += temp * z[k];
            }

            location(afterR, afterC + 2, temp, 3);
            location(afterR, afterC - 2, temp, 3);
            location(nowR + 3 * x[move], nowC + 3 * y[move], temp, 4);
            sum += temp * z[3];
            sum += temp * z[3];
            sum += temp * z[4];
            // sum에는 이제 다 분배된 모래가 들어있음. 이제 나머지는 알파에 넣어야함.
            if (afterR + x[move] < 0 || afterR + x[move] >= n || afterC + y[move] < 0 || afterC + y[move] >= n)
            {
                out += temp - sum;
            }
            else
                g[afterR + x[move]][afterC + y[move]] += temp - sum;
        }
        else if (move == 2)
        { // right
            step += 1;
            for (int k = 0; k < 3; k++)
            {
                location(nowR - 1, nowC + k, temp, k);
                location(nowR + 1, nowC + k, temp, k);
                sum += temp * z[k];
                sum += temp * z[k];
            }
            location(afterR + 2, afterC, temp, 3);
            location(afterR - 2, afterC, temp, 3);
            location(nowR + 3 * x[move], nowC + 3 * y[move], temp, 4);
            sum += temp * z[3];
            sum += temp * z[3];
            sum += temp * z[4];
            // sum에는 이제 다 분배된 모래가 들어있음. 이제 나머지는 알파에 넣어야함.
            if (afterR + x[move] < 0 || afterR + x[move] >= n || afterC + y[move] < 0 || afterC + y[move] >= n)
            {
                out += temp - sum;
            }
            else
                g[afterR + x[move]][afterC + y[move]] += temp - sum;
        }
        else if (move == 3)
        { // up
            step += 1;
            for (int k = 0; k < 3; k++)
            {
                location(nowR - k, nowC + 1, temp, k);
                location(nowR - k, nowC - 1, temp, k);
                sum += temp * z[k];
                sum += temp * z[k];
            }
            location(afterR, afterC + 2, temp, 3);
            location(afterR, afterC - 2, temp, 3);
            location(nowR + 3 * x[move], nowC + 3 * y[move], temp, 4);
            sum += temp * z[3];
            sum += temp * z[3];
            sum += temp * z[4];
            // sum에는 이제 다 분배된 모래가 들어있음. 이제 나머지는 알파에 넣어야함.
            if (afterR + x[move] < 0 || afterR + x[move] >= n || afterC + y[move] < 0 || afterC + y[move] >= n)
            {
                out += temp - sum;
            }
            else
                g[afterR + x[move]][afterC + y[move]] += temp - sum;
        }
        
        //다 이동하면 이제 현재 좌표를 옮겨준다.
        nowR = afterR, nowC = afterC;
        if (nowR == 0 && nowC == 0) //만약 탈출 지점까지 왔다면 while문을 탈출해야함.
        {
            break;
        }
        if (move % 2 == 1 && step == dist) //방향이 2번 바뀔때마다 거리를 1씩 증가시켜줘야함.
        {
            dist = dist + 1; // dist만큼 방향을 전진 시켜야함.
            move = (move + 1) % 4;
            step = 0;
        }
        if (step == dist)
        {
            move = (move + 1) % 4;
            step = 0;
        }
    }
    cout << out; //빠져나간 모래의 양
}
void location(int a, int b, int temp, int k)
{
    if (a < 0 || a >= n || b < 0 || b >= n) //좌표가 이상하다면
        out += temp * z[k];
    else
        g[a][b] += temp * z[k];
}

✔느낀 점

• 참 내가 봐도 더러운 코드였고, 더러운 문제였다.
• 방향을 전환하는 것이 어려웠다.
• 모래를 배분하는 것은  손으로 직접 해보면 쉽게 구할 수 있다.