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

문제 링크: www.acmicpc.net/problem/20057

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

1. 주의할 점

- 토네이도는 1칸씩 계속 움직인다

- 현재 진행방향 기준으로 어떤 방향으로 얼마만큼 퍼지는지 미리 구해놓는다

- 주석으로 '중요' 표시한 2줄의 코드가 중요하다

 

2. 구현

- 모래밭에 대한 정보를 Arr[][] 배열에 담는다

- 8방향에 대한 정보를 dx[], dy[]에 미리 저장한다

- Order[] 배열을 통해 토네이도의 진행방향을 저장해놓는다

- 토네이도 진행방향에 대한 퍼지는 방향과 정도를 미리 init_spread()를 통해 Spread 벡터에 저장한다

- Start() 함수를 통해 토네이도를 1칸씩 움직인다. 종료조건은 현재 좌표가 (0,-1)일때

- 현재 토네이도 위치를 cy,cx를 통해 나타내며, 초기화하고 시작한다. 또한, Cnt를 통해 토네이도가 얼마만큼 어떤 방향으로 움직여야 하는지 구한다

- 토네이도가 해당 방향으로 움직이는 길이를 Len에 할당하고 Len만큼 모래 퍼트리기를 시작한다

- 이동하려는 다음 칸에 모래가 존재하지 않으면 Continue, 존재한다면 퍼트리는 계산을 구한다. 이때, 현재 토네이도가 바라보는 방향을 고려해서 퍼지는 방향을 알아내기 위해, sd는 (Spread[i].dir + 현재방향)%8로 할당한다

- 9개의 범위로 퍼진 이후, a로 이동되는 값을 Remain에 저장한다. 또한, 9개의 범위 혹은 a로 이동되는 좌표가 범위 밖이라면 tot에 추가한다

 

#include <iostream>
#include <vector>
using namespace std;
struct info{
    int dir,len,per;
};
info tmp;
int dx[8]={0,1,1,1,0,-1,-1,-1};
int dy[8]={-1,-1,0,1,1,1,0,-1};
int num,cd,len,cx,cy,cnt;
long long tot=0;
int arr[499][499];
int order[4]={6,4,2,0};
vector<info> spread;

void init_spread(){
    spread.push_back({1,1,10});
    spread.push_back({2,1,7});
    spread.push_back({2,2,2});
    spread.push_back({3,1,1});
    spread.push_back({5,1,1});
    spread.push_back({6,1,7});
    spread.push_back({6,2,2});
    spread.push_back({7,1,10});
    spread.push_back({0,2,5});
}

void start(){
    cnt=0;
    cx = num/2;
    cy = num/2;
    while(1){
        cd = order[(cnt/2)%4];
        len = cnt/4+1;
        for(int k=0;k<len;k++){
            cx+=dx[cd];
            cy+=dy[cd];
            if(cy==0 && cx==-1)    break;
            int cur = arr[cy][cx];
            if(cur==0) continue;
            
            arr[cy][cx]=0;		//현재 위치 0으로 만들기(중요)
            int leave=0;
            for(int i=0;i<9;i++){
                int sd = (spread[i].dir+cd)%8;		//중요
                int sl = spread[i].len;
                int sp = spread[i].per;
                int val = (int)(cur*sp)/100;
                int nx = cx+dx[sd]*sl;
                int ny = cy+dy[sd]*sl;
                leave+=val;
                if(nx>=0 && ny>=0 && nx<num && ny<num)  arr[ny][nx]+=val;       //범위 안
                else    tot+=val;       //범위 밖
            }
            int nnx = cx+dx[cd];
            int nny = cy+dy[cd];
            int remain = cur-leave;
            if(nnx>=0 && nny>=0 && nnx<num && nny<num)  arr[nny][nnx]+=remain;       //범위 안
            else    tot+=remain;       //범위 밖
        }
        cnt+=2;
        if(cx==-1 && cy==0) break;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>num;
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++)
            cin>>arr[i][j];
    init_spread();
    start();
    cout<<tot;
    return 0;
}