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

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

 

토네이도 생겨먹은 게 귀찮아보여서 안풀다가 드디어 풀었다.

 

토네이도는 중심에서부터 진행하는데 currD와 l을 변경해주면서 보드 전체를 돌게 했다.

 

이걸 어떻게 구현할까.. 하다가 현재 위치(위 그림의 y 위치)에서 currD 방향(x -> y 방향), currD의 시계방향(위 그림의 y -> 위쪽 7% 방향)을 축으로 잡아서 축마다의 이동거리를 저장했다.

windNode의 dd는 currD 방향으로의 이동거리, dcw는 currD의 시계방향으로의 이동거리, r은 이동하는 모래의 비율

 

이동한 모래들의 총량을 sum에 저장하여 a로 이동한 모래를 구했다.

 

토네이도가 보드 전체를 다 휩쓸고 난 후 손실된 모래 양이 ans

 

#include <iostream>

using namespace std;

typedef struct windNode{
    int dd;
    int dcw;
    double r;
}windNode;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// 시계방향 (상하좌우 => 우좌상하)
int cw[] = {3, 2, 0, 1};

// 반시계방향 (상하좌우 => 좌우하상)
int ccw[] = {2, 3, 1, 0};

int n;
int board[499][499];
int totalSand;
int currX, currY, currD;
int ans;
bool done;

windNode w[9] = {
    {2, 0, 0.05},
    {1, 1, 0.10},
    {1, -1, 0.10},
    {0, 1, 0.07},
    {0, -1, 0.07},
    {0, 2, 0.02},
    {0, -2, 0.02},
    {-1, 1, 0.01},
    {-1, -1, 0.01}
};

bool isValid(int x, int y){
    if(x < 0 || x >= n || y < 0 || y >= n) return false;
    return true;
}
void moveTornado(){
    
    int nxtX = currX + dx[currD];
    int nxtY = currY + dy[currD];
    
    if(!isValid(nxtX, nxtY)){
        done = true;
        return;
    }
    
    currX = nxtX;
    currY = nxtY;
    
    int a = board[currX][currY];
    board[currX][currY] = 0;
    
    int sum = 0; // a에서 손실된 모래양
    for(int i=0; i<9; i++){
        windNode curr = w[i];
        
        int x = currX, y = currY;
        x += curr.dd * dx[currD];
        y += curr.dd * dy[currD];
        
        x += curr.dcw * dx[cw[currD]];
        y += curr.dcw * dy[cw[currD]];
        
        int sand = static_cast<double>(a) * curr.r;
       
        if(isValid(x, y)){
            board[x][y] += sand;
        }
        
        sum += sand;
        
    }
    a -= sum;
    
    int ax = currX + dx[currD];
    int ay = currY + dy[currD];
    
    if(!isValid(ax, ay)) return;
    
    board[ax][ay] += a;
    
    return;
}

void solve(){
    int l = 1;
    
    currX = currY = n / 2;
    currD = 2; // left
    
    while(!done){
        for(int i=0; i<2 && !done; i++){
            for(int j=0; j<l; j++){
                moveTornado();
            }
            currD = ccw[currD];
        }
        l++;
    }
    
    int leftSand = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            leftSand += board[i][j];
        }
    }
    
    ans = totalSand - leftSand;
    
    return;
}

int main(){
    cin >> n;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> board[i][j];
            
            totalSand += board[i][j];
        }
    }
    
    solve();
    

    cout << ans;
    
    return 0;
}