[ BOJ - 20057번 ] 마법사 상어와 토네이도 (C++)

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

 

[ 풀이 방법 ]

1. 토네이도 이동 기능

  - 토네이도의 이동은 NxN 배열의 중앙에서 시작한다.

  - 토네이도는 좌 -> 하 -> 우 -> 상 순서로 이동한다.

  - 토네이도의 이동 횟수는 1칸 이동 2번, 2칸 이동 2번, 3칸 이동 2번 · · · 과 같은 패턴이 반복된다.

  - 토네이도가 (0, 0)에 도달하면 이동이 종료된다.

 

-> 전역변수 x, y를 이용해 토네이도의 현재 좌표를 저장한다.

-> 좌 -> 하 -> 우 -> 상 순서로 패턴에 맞는 횟수의 이동을 처리(rotate)

 

2. 토네이도의 이동에 따른 모래의 이동 기능

  - 토네이도가 한 칸 이동하면 토네이도가 이동한 위치의 모래가 문제에서 주어진 조건에 맞춰 이동하게 된다.

  - 이동 방향에 따라 처리(좌 우 or 상 하)

 

토네이도의 현재 위치가 (x, y), 토네이도가 이동할 위치가 (nx, ny), 이동 방향이 좌 or 우라고 가정했을 때,

1. (x±1, y)로 (nx, ny)위치의 1%의 모래가 이동

2. (x±1, ny)로 (nx, ny)위치의 7%의 모래가 이동

3. (x±2, ny)로 (nx, ny)위치의 2%의 모래가 이동

4. (x±1, ny±1)로 (nx, ny)위치의 10%의 모래가 이동

5. (x, ny±2)로 (nx, ny)위치의 5%의 모래가 이동

6. (x, ny±1)로 (nx, ny)위치에 남은 모래가 이동

- 이동한 모래만큼 (nx, ny)위치의 모래가 감소한다.

- 모래가 이동할 위치가 격자의 밖이라면, 밖으로 벗어난 모래의 양에 이동해야 하는 모래의 양을 더해준다.

- 상 하로의 이동은 위 기능에서 x와 y를 반대로 적용하여 구현한다.

 

-> 2차원 배열(board)을 이용해 모래의 위치와 양을 저장한다.

-> 전역변수 res를 이용해 밖으로 벗어난 모래의 양을 저장한다.

-> 토네이도의 이동과 토네이도의 이동에 따른 모래의 이동을 처리(move)

 

3. 위 기능들을 토네이도의 이동이 끝날 때까지 반복한다.

 

[ 회고 ]

 토네이도의 이동에 따른 모래의 이동 기능을 하드 코딩하였지만, 자세하게 구현 계획을 세워두었기 때문에 오류나 실수 없이 정확히 구현하여 한번에 정담을 맞출 수 있었다.

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N;

int x; int y;
vector<vector<int>> sand;

int dirX[4] = {0, 1, 0, -1};
int dirY[4] = {-1, 0, 1, 0};

int moveCnt = 1;
bool arrive = false;
int res;

void move(int dir) {
    
    int nx = x + dirX[dir];
    int ny = y + dirY[dir];
    
    if(nx != x) {
        int t = sand[nx][ny];
        
        t -= int(sand[nx][ny]*0.01);
        if(y-1 < 0) res += int(sand[nx][ny]*0.01);
        else sand[x][y-1] += int(sand[nx][ny]*0.01);
        
        t -= int(sand[nx][ny]*0.01);
        if(y+1 >= N) res += int(sand[nx][ny]*0.01);
        else sand[x][y+1] += int(sand[nx][ny]*0.01);
        
        t -= int(sand[nx][ny]*0.07);
        if(y-1 < 0) res += int(sand[nx][ny]*0.07);
        else sand[nx][y-1] += int(sand[nx][ny]*0.07);
        
        t -= int(sand[nx][ny]*0.07);
        if(y+1 >= N) res += int(sand[nx][ny]*0.07);
        else sand[nx][y+1] += int(sand[nx][ny]*0.07);
        
        t -= int(sand[nx][ny]*0.02);
        if(y-2 < 0) res += int(sand[nx][ny]*0.02);
        else sand[nx][y-2] += int(sand[nx][ny]*0.02);
        
        t -= int(sand[nx][ny]*0.02);
        if(y+2 >= N) res += int(sand[nx][ny]*0.02);
        else sand[nx][y+2] += int(sand[nx][ny]*0.02);
        
        t -= int(sand[nx][ny]*0.1);
        if(y-1 < 0 ||
           (nx + dirX[dir] < 0 || nx + dirX[dir] >= N)) res += int(sand[nx][ny]*0.1);
        else sand[nx + dirX[dir]][y-1] += int(sand[nx][ny]*0.1);
        
        t -= int(sand[nx][ny]*0.1);
        if(y+1 >= N ||
           (nx + dirX[dir] < 0 || nx + dirX[dir] >= N)) res += int(sand[nx][ny]*0.1);
        else sand[nx + dirX[dir]][y+1] += int(sand[nx][ny]*0.1);
        
        t -= int(sand[nx][ny]*0.05);
        if(nx + 2*dirX[dir] < 0 || nx + 2*dirX[dir] >= N) res += int(sand[nx][ny]*0.05);
        else sand[nx + 2*dirX[dir]][y] += int(sand[nx][ny]*0.05);
        
        if(nx + dirX[dir] < 0 || nx + dirX[dir] >= N) res += t;
        else sand[nx + dirX[dir]][y] += t;
        
        sand[nx][ny] = 0;
    }
    
    if(ny != y) {
        int t = sand[nx][ny];
        
        t -= int(sand[nx][ny]*0.01);
        if(x-1 < 0) res += int(sand[nx][ny]*0.01);
        else sand[x-1][y] += int(sand[nx][ny]*0.01);
        
        t -= int(sand[nx][ny]*0.01);
        if(x+1 >= N) res += int(sand[nx][ny]*0.01);
        else sand[x+1][y] += int(sand[nx][ny]*0.01);
        
        t -= int(sand[nx][ny]*0.07);
        if(x-1 < 0) res += int(sand[nx][ny]*0.07);
        else sand[x-1][ny] += int(sand[nx][ny]*0.07);
        
        t -= int(sand[nx][ny]*0.07);
        if(x+1 >= N) res += int(sand[nx][ny]*0.07);
        else sand[x+1][ny] += int(sand[nx][ny]*0.07);
        
        t -= int(sand[nx][ny]*0.02);
        if(x-2 < 0) res += int(sand[nx][ny]*0.02);
        else sand[x-2][ny] += int(sand[nx][ny]*0.02);
        
        t -= int(sand[nx][ny]*0.02);
        if(x+2 >= N) res += int(sand[nx][ny]*0.02);
        else sand[x+2][ny] += int(sand[nx][ny]*0.02);
        
        t -= int(sand[nx][ny]*0.1);
        if(x-1 < 0 ||
           (ny + dirY[dir] < 0 || ny + dirY[dir] >= N)) res += int(sand[nx][ny]*0.1);
        else sand[x-1][ny + dirY[dir]] += int(sand[nx][ny]*0.1);
        
        t -= int(sand[nx][ny]*0.1);
        if(x+1 >= N ||
           (ny + dirY[dir] < 0 || ny + dirY[dir] >= N)) res += int(sand[nx][ny]*0.1);
        else sand[x+1][ny + dirY[dir]] += int(sand[nx][ny]*0.1);
        
        t -= int(sand[nx][ny]*0.05);
        if(ny + 2*dirY[dir] < 0 || ny + 2*dirY[dir] >= N) res += int(sand[nx][ny]*0.05);
        else sand[x][ny + 2*dirY[dir]] += int(sand[nx][ny]*0.05);
        
        if(ny + dirY[dir] < 0 || ny + dirY[dir] >= N) res += t;
        else sand[x][ny + dirY[dir]] += t;
        
        sand[nx][ny] = 0;
    }
    
    x = nx;
    y = ny;
    if(!x && !y) {
        arrive = true;
        return;
    }
}

void rotate() {
    
    for(int i = 0; i < 4; i++) {
        if(i == 2) moveCnt++;
        for(int j = 0; j < moveCnt; j++) {
            move(i);
            if(arrive) return;
        }
    }
    moveCnt++;
}

void solve(){
    
    while(!arrive) {
        rotate();
    }
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    


    cin >> N;
    sand.resize(N, vector<int>(N));
    x = y = N/2;

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


    solve();

    cout << res << '\n';
    
    return 0;
}