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

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

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

마법사 상어가 해리포터처럼 시리즈물로 나오네요

 

소요 시간

골드 2 기준으로 맞았습니다! 까지 77분이 소요되었습니다.

구현 자체가 어려운 문제는 아니지만 방향마다 모래가 다르게 퍼지기 때문에 이 부분을 구현하기 까다롭습니다. 실수하기 좋은 대표적인 문제인듯 합니다.

 

구상

필요한 함수는 많지 않습니다.

1. 토네이도 모양으로 모든 칸을 순회하는 함수

2. y의 좌표와 x로부터의 방향이 주어졌을 때, 모래를 아래와 같이 퍼트리는 함수

(함수 1에서 회오리감자처럼 순회하면서 각 칸마다 2를 호출하면 됩니다.)

 

토네이도 순회

저는 위와 같은 규칙성을 찾아서 그대로 구현했습니다.

 

상하좌우 모래 이동

말로 설명하기가 어려워서 문제 풀 때 사용한 구상종이를 첨부합니당.^^; 각 방향으로 모래가 흩어질 때 모래를 가산해야 하는 좌표값들을 delta값 배열로 저장했습니다.

 

 

코드

#include <string>
#include <vector>
#include<iostream>
#include <climits>
#include<set>
#include<cmath>
#include<algorithm>

using namespace std;

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

int ddx[4][10] = {{-2,-1,-1,-1,0,1,1,1,2,0}, {0,1,0,-1,2,1,0,-1,0,1}, {-2,-1,-1,-1,0,1,1,1,2,0}, {0,-1,0,1,-2,-1,0,1,0,-1}};

int ddy[4][10] = {{0,-1,0,1,-2,-1,0,1,0,-1}, {2,1,1,1,0,-1,-1,-1,-2,0}, {0,1,0,-1,2,1,0,-1,0,1}, {2,1,1,1,0,-1,-1,-1,-2,0}};
int rate[9] = {2, 10, 7, 1, 5, 10, 7, 1, 2};

int move_sands(int N, int tox, int toy, int dir, vector<vector<int> >& sand) { //움직이고 밖으로 나간 것들은 리턴
    int out = 0;
    int s = sand[tox][toy];
    int total = 0;
    for(int i=0; i<9; i++) {
        int nx = tox + ddx[dir][i]; int ny = toy + ddy[dir][i];
        if(nx < 0 || nx > N-1 || ny < 0 || ny > N-1) out += (s*rate[i]*(0.01));
        else sand[nx][ny] += s*rate[i]*(0.01);
        total += s*rate[i]*(0.01);
    }
    int nx = tox + ddx[dir][9]; 
    int ny = toy + ddy[dir][9]; 
    if(nx < 0 || nx > N-1 || ny < 0 || ny > N-1) out += (s-total);
    else sand[nx][ny] += (s-total);

    sand[tox][toy] = 0;

    return out;
}

int make_to(int N, vector<vector<int> >& sand) {
    int out = 0;
    int x = N/2; int y = N/2;
    for(int i=1; i<N; i += 2) {
        for(int j=i; j>0; j--) {
            x = x + dx[0]; y = y + dy[0];
            out += move_sands(N, x, y, 0, sand);
        }
        for(int j=i; j>0; j--) {
            x = x + dx[1]; y = y + dy[1];
            out += move_sands(N, x, y, 1, sand);
        }
        for(int j=i+1; j>0; j--) {
            x = x + dx[2]; y = y + dy[2];
            out += move_sands(N, x, y, 2, sand);
        }
        for(int j=i+1; j>0; j--) {
            x = x + dx[3]; y = y + dy[3];
            out += move_sands(N, x, y, 3, sand);
        }
    }
    for(int j=N-1; j>0; j--) {
        x = x + dx[0]; y = y + dy[0];
        out += move_sands(N, x, y, 0, sand);
    }
    return out;
}

int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int N;
    cin >> N;
    vector<vector<int> > sand;
    sand.resize(N);
    for(int i=0; i<N; i++) {
        sand[i].resize(N);
        for(int j=0; j<N; j++) {
            cin >> sand[i][j];
        }
    }
    cout << make_to(N, sand) << endl;

    return 0;
}