20057번 - 마법사 상어와 토네이토

문제

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

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

---

접근방법

1) 접근 사고

태풍에 대한 구조체를 두어 태풍의 이동을 계산하기 쉽게 작성했다. 

1. 태풍이 이동한다.

2. 이동한 위치에 모래가 존재한 지 파악한다. 모래가 있을 경우 태풍의 구조체 중 c.perBoard에 담긴 수치 값을 활용하여 비율에 맞게 모래를 전파한다. 없을 경우 다음 탐색으로 넘어간다.

3. 범위가 초과하여 합계에 더 해줘야 하는지 board에 더해줘야 하는지 구분한다.

4. 이과정을 반복한다.

 

2) 시간 복잡도

O(n ^ 2)

 

3) 실수

1. 태풍의 경로마다 모든 경우를 검색해줘야 하는데 태풍이 꺾이는 점 위치로만 이동을 하여 잘못된 알고리즘 작성

2. perBoard[i][i]같은 인덱스를 잘못 두는 오류(진짜 나 왜 살지??)

 

4) PS

2번 실수 때문에 하루 다 낭비했다. 어금니 꽉 깨물고 디버깅했는데... 디버깅 전에 저런 게 눈에 왜 안 보이는지 너무 슬프다.

---

정답 코드

#include <bits/stdc++.h>
 
using namespace std;
const int MAX = 501;
 
int my[] = {0, 1, 0, -1};
int mx[] = {-1, 0, 1, 0};
 
struct cane {
    int y, x;
    double perboard[5][5];
};
 
struct play {
    int n;
    int sum;
    cane c;
    int board[MAX][MAX];
 
    play(int n) : n(n), sum(0) {}
 
    //입력값, 토네이토로 인해 날아가나는 위치별 비율값 설정
    void init() {
        memset(board, 0, sizeof board);
        memset(c.perboard, 0, sizeof c.perboard);
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> board[i][j];
            }
        }
 
        c.y = n / 2;
        c.x = n / 2;
        c.perboard[0][2] = 0.02;
        c.perboard[1][1] = 0.1, c.perboard[1][2] = 0.07, c.perboard[1][3] = 0.01;
        c.perboard[2][0] = 0.05, c.perboard[2][1] = 0.55;
        c.perboard[3][1] = 0.1, c.perboard[3][2] = 0.07, c.perboard[3][3] = 0.01;
        c.perboard[4][2] = 0.02;
    }
 
    //범위 초과 학인 함수
    bool isValid(int y, int x) {
        return (y >= 0 && y < n && x >= 0 && x < n);
    }
 
    //태풍을 이동시키면서 비율에 맞게 모래를 뿌리는 함수
    void moveCane() {
        int s = 1, dir = 0;
        while (1) {
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < s; j++) {
                    if (c.y == 0 && c.x == 0) {
                        return;
                    }
                    c.y += my[dir];
                    c.x += mx[dir];
 
                    int curSand = board[c.y][c.x];
                    board[c.y][c.x] = 0;
                    if (curSand == 0)
                        continue;
 
                    for (int i = -2; i <= 2; i++) {
                        for (int j = -2; j <= 2; j++) {
                            double curPercent = c.perboard[i + 2][j + 2];
 
                            int moveSand;
                            //알파의 범위는 먼지가 날리가 남은 만큼이다.
                            if (curPercent >= 0.55) {
                                moveSand = curSand
                                        - floor(curSand * 0.02) * 2
                                        - floor(curSand * 0.07) * 2
                                        - floor(curSand * 0.10) * 2
                                        - floor(curSand * 0.01) * 2
                                        - floor(curSand * 0.05);
                            } else {
                                moveSand = floor(curSand * curPercent);
                            }
 
                            int nextY = c.y + i;
                            int nextX = c.x + j;
                            //범위를 초과해 정답에 더해야 하는경우
                            if (!isValid(nextY, nextX)) {
                                sum += moveSand;
                            } else
                                board[nextY][nextX] += moveSand;
                        }
                    }
                }
                dir++;
                if (dir == 4)
                    dir = 0;
                rotateCane();
            }
            s++;
        }
    }
 
    //태풍을 회전시키는 함수
    void rotateCane() {
        double tmpboard[5][5];
        memcpy(tmpboard, c.perboard, sizeof tmpboard);
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                c.perboard[5 - j - 1][i] = tmpboard[i][j];
            }
        }
    }
 
    //디버깅용
    void printBoard() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << board[i][j] << " ";
            }
            cout << "\n";
        }
        cout << "==============" << "\n";
    }
};
 
int main() {
    int n;
    cin >> n;
    play op(n);
    op.init();
    op.moveCane();
    cout << op.sum << "\n";
}