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

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

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

 

 

[난이도] Gold3
[유형] 시뮬레이션

[풀이]
우선 토네이도의 규칙성을 파악해야 합니다.
<-,ㅜ,->,ㅗ 방향을 각각 0,1,2,3 이라고 정하고
격자의 크기가 N일 때, (N/2+1,N/2+1) 에서부터
0->1->2->3->0 순서로 방향을 바꾸며 진행됩니다.
각 방향으로 진행하는 횟수는 1,1,2,2,3,3,4,4....N-1,N-1,N-1 로
방향이 2회 바뀔때마다 횟수가 1번씩 늘어나며 마지막 N-1번 진 행할때는 3번 방향이 바뀝니다.

위를 이용해 시뮬레이션을 해주면 되는데

map<int,vector<pair<int,int>>> table =
{
    {1,{{1,1},{-1,1}}},
    {2,{{2,0},{-2,0}}},
    {7,{{1,0},{-1,0}}},
    {10,{{1,-1},{-1,-1}}},
    {5,{{0,-2}}}
};

위와 같이 현재 방향이 0일때의 {퍼센트,{토네이도로부터의 상대좌표}} 들을 map을 이용해 저장해 놓고
시계방향으로 90도 회전할때마다 (y,x) -> (-x,y)로 좌표들을 변경해서 이용해주면 됩니다.
즉, 방향이 0일때는 0번, 1일때는 1번, 2일때는 2번, 3일때는 3번 회전시켜주면 되므로
위의 1개의 테이블만 정의해주면 됩니다.

 

#include <map>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
int N,board[501][501],ans;
int dy[4] = {0,1,0,-1};
int dx[4] = {-1,0,1,0};
map<int,vector<pair<int,int>>> table = 
{
    {1,{{1,1},{-1,1}}},
    {2,{{2,0},{-2,0}}},
    {7,{{1,0},{-1,0}}},
    {10,{{1,-1},{-1,-1}}},
    {5,{{0,-2}}}
};
pair<int,int> cvt(int dir,int y,int x){
    for(int i=0;i<dir;i++) {
        int ny=-x,nx=y;
        y=ny,x=nx;
    }
    return {y,x};
}
void update(int dir,int fy,int fx){
    int total=board[fy][fx];
    int erased=0;
    for(auto [k,v] : table){
        for(auto p : v){
            auto c = cvt(dir,p.first,p.second);
            int ny=fy+c.first, nx=fx+c.second;
            int r = total*(k/100.0);
            erased+=r;
            if(ny>=1&&nx>=1&&ny<=N&&nx<=N) board[ny][nx]+=r;
            else ans+=r;
        }
    }
    board[fy][fx]=0;
    int ty=fy+dy[dir],tx=fx+dx[dir];
    if(ty>=1&&tx>=1&&ty<=N&&tx<=N) board[ty][tx]+=total-erased;
    else ans+=total-erased;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) scanf("%d",&board[i][j]);
    int cy=N/2+1,cx=N/2+1,dir=0;
    for(int i=1;i<N;i++){
        int cnt=2;
        if(i==N-1) cnt=3;
        for(int j=0;j<cnt;j++){
            for(int k=0;k<i;k++){
                cy+=dy[dir];
                cx+=dx[dir];
                update(dir,cy,cx);
            }
            dir=(dir+1)%4;
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/20057.cpp