마법사 상어와 토네이도

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 0511 ~ 0747 
int N,ans;
int board[505][505];
/* 순방향인 경우 */
int dr_h_p[8] = {-1, -1 ,-1, -2, 1, 1, 1, 2};
int dc_h_p[8] = {-1, 0, 1, 0, -1, 0, 1, 0};
int dr_v_p[8] = {1, 0, -1, 0, 1, 0, -1, 0};
int dc_v_p[8] = {-1, -1, -1, -2, 1, 1, 1, 2};
int rate_p[8] = {10, 7, 1, 2, 10, 7, 1, 2};
/* 역방향인 경우 */
int dr_h_n[8] = {-1, -1 ,-1, -2, 1, 1, 1, 2};
int dc_h_n[8] = {-1, 0, 1, 0, -1, 0, 1, 0};
int dr_v_n[8] = {1, 0, -1, 0, 1, 0, -1, 0};
int dc_v_n[8] = {-1, -1, -1, -2, 1, 1, 1, 2};
int rate_n[8] = {1, 7, 10, 2, 1, 7, 10, 2};

bool checkPos(int r, int c){
    if(r<1 or c<1 or r>N or c>N) return false;
    return true;
}
void spread(int r, int c, bool pos, bool horizon)
{
    int origin = board[r][c];
    int sum = 0;
    /* 대칭인 8개 좌표 처리 */
    for(int dir=0;dir<8;dir++)
    {
        int nr = r;
        int nc = c;
        int R ;     
        if(horizon == true){
            if(pos == true){
                nr += dr_h_p[dir];
                nc += dc_h_p[dir];
                R = rate_p[dir];
            }else{
                nr += dr_h_n[dir];
                nc += dc_h_n[dir];
                R = rate_n[dir];
            }
        }else{
            if(pos == true){
                nr += dr_v_p[dir];
                nc += dc_v_p[dir];
                R = rate_p[dir];
            }else{
                nr += dr_v_n[dir];
                nc += dc_v_n[dir];
                R = rate_n[dir];
            }
        }
        int mount = origin*R/100;
        sum += mount;
        /* 범위를 벗어나는 모래를 답에 추가 */
        if(nr<1 or nc<1 or nr>N or nc>N){
            ans += mount;
            continue;
        }
        board[nr][nc] += mount;
    }
    /* 방향에 따라 2좌표 처리 */
    int nr = r;
    int nc = c;
    int save = origin - sum - origin*5/100;
    if(horizon == true){
        if(pos == true){
            if(checkPos(r,c-1))
                board[r][c-1] += save;
            else ans += save;
            board[r][c] = 0;
            if(checkPos(r,c-2)){
                board[r][c-2] += origin*5/100;
            }
            else ans += origin*5/100;
        }else{
            if(checkPos(r,c+1))
                board[r][c+1] += save;
            else ans += save;
            board[r][c] = 0;
            if(checkPos(r,c+2))
                board[r][c+2] += origin*5/100;
            else ans += origin*5/100;
        }
    }else{
        if(pos == true){
            if(checkPos(r+1,c))
                board[r+1][c] += save;
            else ans += save;
            board[r][c] = 0;
            if(checkPos(r+2,c))
                board[r+2][c] += origin*5/100;
            else ans += origin*5/100;
        }else{
            if(checkPos(r-1,c))
                board[r-1][c] += save;
            else ans += save;
            board[r][c] = 0;
            if(checkPos(r-2,c))
                board[r-2][c] += origin*5/100;
            else ans += origin*5/100;
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            cin >> board[i][j];

    int size = 0;
    int st,en;
    int left_R = N/2+1;
    int down_C = N/2;
    int right_R = N/2+2;
    int up_C = N/2+2;            
    while(true)
    {
        /* 왼쪽 방향 */
        st = min(N/2 + size, N);
        en = max(1, N/2 - size);
        for(int i=st;i>=en;i--)
        {
            spread(left_R, i, true, true);
        }
        /* 아래 방향 */
        st = max(N/2+2 - size,1);
        en = min(N/2+2 + size, N);
        for(int i=st;i<=en;i++)
        {
            spread(i, down_C, true, false);
        }

        /* 오른쪽 방향 */
        st = max(N/2+1 - size,1);
        en = min(N/2+1+1 + size, N);
        for(int i=st;i<=en;i++)
        {
            spread(right_R, i, false, true);
        }

        /* 위쪽 방향 */
        st = min(N/2+1+size, N);
        en = max(N/2 - size ,1);
        for(int i=st;i>=en;i--)
        {
            spread(i, up_C, false, false);
        }
        left_R--;
        down_C--;
        right_R++;
        up_C++;
        size++;
        if(left_R == 0) break;
    }
    cout << ans;
    return 0;
}

• 핵심
  • 토네이도 방향에 따라 board[][]에 접근하는 것
  • 토네이도 방향에 따라 각자의 spread와 rate를 지정하는 것

• 깨달은 것
  • 토네이도 방향이 4가지이니까 dir[4][10]으로 모두 지정했다면 코드가 더 짧을 것이고 지금처럼 시간이 오래걸리지 않을 것 같다
  • 토네이도 방향에 맞춰서 board[][]판에 접근하는 것을 구현할 때 각 방향에서 사용하는 변수를 사용하면 좋다
    (지금 코드의 left_r, down_c 등등!)