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

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

문제에 주어진 조건을 통해 구현을 하는 문제이다. 두가지 조건을 구현을 해주면 된다. 첫번째는 토네이도의 이동, 두번째는 모래의 이동이다. 토에니도의 이동은 왼쪽, 아래쪽, 오른쪽, 위쪽 순으로 스텝을 나누어 구현해주었다. 한바퀴마다 이동하는 칸이 두개씩 늘어나고 오른쪽과 위쪽의 경우 왼쪽과 아래쪽보다 1칸씩 더 이동한다는 점을 move를 이용한 반복문을 통해 구현해주었다. 그리고 모래의 이동의 경우 깔끔하게 표현할 방식을 찾지 못해 하나씩 구현해주었다. 도착 지점의 경우 step1에서 도달하게 되므로 step1을 끝낸 후 좌표를 확인해 멈춰주었다. 격자를 나간 모래의 양은 배열 자체의 크기를 N+4, N+4로 가져서 범위를 나간 모래들을 모두 구해 출력해주었다.
역시 구현의 경우는 시간이 오래 걸리는 문제 유형이다. 구현 자체는 어렵지 않은데 사실상 노가다라 시간이 굉장히 오래 걸린 문제였다. 그리고 문제를 잘못 읽는 바람에 모래의 이동 조건을 잘못 생각한 점도 있었다. 구현 문제를 풀때는 조건을 제대로 이해하는 것이 가장 중요하다는 점을 인지하자.

#include <iostream>

using namespace std;

int N, y, x, result = 0;
int A[504][504];

void step1(int move) {
    while (move--) {
        int sand = A[y][x - 1];
        int tmp = sand;

        A[y - 1][x] += sand * 0.01;
        tmp -= (int)(sand * 0.01);
        A[y + 1][x] += sand * 0.01;
        tmp -= (int)(sand * 0.01);
        A[y - 1][x - 1] += sand * 0.07;
        tmp -= (int)(sand * 0.07);
        A[y + 1][x - 1] += sand * 0.07;
        tmp -= (int)(sand * 0.07);
        A[y - 2][x - 1] += sand * 0.02;
        tmp -= (int)(sand * 0.02);
        A[y + 2][x - 1] += sand * 0.02;
        tmp -= (int)(sand * 0.02);
        A[y - 1][x - 2] += sand * 0.1;
        tmp -= (int)(sand * 0.1);
        A[y + 1][x - 2] += sand * 0.1;
        tmp -= (int)(sand * 0.1);
        A[y][x - 3] += sand * 0.05;
        tmp -= (int)(sand * 0.05);

        A[y][x - 2] += tmp;
        A[y][x - 1] = 0;

        x--;
        if (y == 2 && x == 2) break;
    }
}

void step2(int move) {
    while (move--) {
        int sand = A[y + 1][x];
        int tmp = sand;

        A[y][x - 1] += sand * 0.01;
        tmp -= (int)(sand * 0.01);
        A[y][x + 1] += sand * 0.01;
        tmp -= (int)(sand * 0.01);
        A[y + 1][x - 1] += sand * 0.07;
        tmp -= (int)(sand * 0.07);
        A[y + 1][x + 1] += sand * 0.07;
        tmp -= (int)(sand * 0.07);
        A[y + 1][x - 2] += sand * 0.02;
        tmp -= (int)(sand * 0.02);
        A[y + 1][x + 2] += sand * 0.02;
        tmp -= (int)(sand * 0.02);
        A[y + 2][x - 1] += sand * 0.1;
        tmp -= (int)(sand * 0.1);
        A[y + 2][x + 1] += sand * 0.1;
        tmp -= (int)(sand * 0.1);
        A[y + 3][x] += sand * 0.05;
        tmp -= (int)(sand * 0.05);

        A[y + 2][x] += tmp;
        A[y + 1][x] = 0;
        y++;
    }
}

void step3(int move) {
    while(move--) {
        int sand = A[y][x + 1];
        int tmp = sand;

        A[y - 1][x] += sand * 0.01;
        tmp -= (int)(sand * 0.01);
        A[y + 1][x] += sand * 0.01;
        tmp -= (int)(sand * 0.01);
        A[y - 1][x + 1] += sand * 0.07;
        tmp -= (int)(sand * 0.07);
        A[y + 1][x + 1] += sand * 0.07;
        tmp -= (int)(sand * 0.07);
        A[y - 2][x + 1] += sand * 0.02;
        tmp -= (int)(sand * 0.02);
        A[y + 2][x + 1] += sand * 0.02;
        tmp -= (int)(sand * 0.02);
        A[y - 1][x + 2] += sand * 0.1;
        tmp -= (int)(sand * 0.1);
        A[y + 1][x + 2] += sand * 0.1;
        tmp -= (int)(sand * 0.1);
        A[y][x + 3] += sand * 0.05;
        tmp -= (int)(sand * 0.05);

        A[y][x + 2] += tmp;
        A[y][x + 1] = 0;
        x++;
    }
}

void step4(int move) {
    while (move--) {
        int sand = A[y - 1][x];
        int tmp = sand;

        A[y][x - 1] += sand * 0.01;
        tmp -= (int)(sand * 0.01);
        A[y][x + 1] += sand * 0.01;
        tmp -= (int)(sand * 0.01);
        A[y - 1][x - 1] += sand * 0.07;
        tmp -= (int)(sand * 0.07);
        A[y - 1][x + 1] += sand * 0.07;
        tmp -= (int)(sand * 0.07);
        A[y - 1][x - 2] += sand * 0.02;
        tmp -= (int)(sand * 0.02);
        A[y - 1][x + 2] += sand * 0.02;
        tmp -= (int)(sand * 0.02);
        A[y - 2][x - 1] += sand * 0.1;
        tmp -= (int)(sand * 0.1);
        A[y - 2][x + 1] += sand * 0.1;
        tmp -= (int)(sand * 0.1);
        A[y - 3][x] += sand * 0.05;
        tmp -= (int)(sand * 0.05);

        A[y - 2][x] += tmp;
        A[y - 1][x] = 0;
        y--;
    }
}

void solution() {
    y = (N + 4) / 2;
    x = (N + 4) / 2;
    int step = 1;

    while (1) {
        step1(step);

        if (y == 2 && x == 2) break;

        step2(step);
        step3(step + 1);
        step4(step + 1);

        step += 2;
    }

    for (int i = 0; i < N + 4; i++) {
        for (int j = 0; j < N + 4; j++) {
            if (i >= 2 && i < N + 2 && j >= 2 && j < N + 2) continue;
            result += A[i][j];
        }
    }

    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    for (int i = 2; i < N + 2; i++) {
        for (int j = 2; j < N + 2; j++) {
            cin >> A[i][j];
        }
    }

    solution();

    return 0;
}