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

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

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

문제요약

모래의 양이 표시된 격자가 있고, 토네이도가 격자 안을 돌아 나간다. 토네이도는 모래를 주어진 규칙에 맞게 흩뿌리면서 지나가는데, 이때  토네이도가 최종적으로 격자끝에 도달했을 때, 격자 바깥으로 나간 모래의 양을 구하는 시뮬레이션 문제

문제 해결

문제에서 흩뿌리는 정보가 토네이도 현재위치 기준으로 주어졌으므로, 먼저 토네이도의 위치변화를 문제의 주어진 조건에 맞게 만들었다.

까다로웠던 점은 모래가 흩어지는 정도를 나타낸 표가 대칭적이지 않기 때문에 토네이도가 움직이는 방향에 따라, 표도 같이 회전을 해야 했다. 하지만 위/아래, 오른쪽/왼쪽은 서로 대칭이었기 때문에 이를 이용하였다.
토네이도의 현재 위치를 0,0으로 두고, 모래가 흩뿌려지는 상대적 위치들을 pair의 vector에 저장했다. 각각 왼쪽방향으로 움직일때, 아래방향으로 움직일때 두개를 만들어서 저장했고, 오른쪽 방향과 위쪽방향은  -1을 곱해서 사용할 수 있을 것이라고 생각했다. 

최종적으로 반복문을 돌면서 처음에 구했던 토네이도의 경로들을 입력으로 하면 격자내의 모래의 양을 업데이트 해주었고, 마지막에는 남아있는 모래의 양을 최초의 모래양에서 빼주었다.

구현

#include <iostream>
#include <vector>

using namespace std;

int N;

vector<pair<int,int>> left_coords = {{-1,1}, {1,1}, {-2,0}, {2,0}, {-1,0}, {1,0}, {-1,-1}, {1,-1}, {0,-2}, {0,-1}};
vector<pair<int,int>> down_coords = {{-1,-1}, {-1,1}, {0,-2}, {0,2}, {0,-1}, {0,1}, {1,-1}, {1,1}, {2,0}, {1,0}};
vector<int> percentage = {1,1,2,2,7,7,10,10,5};

void conv_leftright(vector< vector<int> > &arr, bool is_leftdown, int start_i, int start_j){
    int total = arr[start_i][start_j];
    arr[start_i][start_j] = 0;
    
    int sign = 1;
    if(!is_leftdown) sign = -1; 
    
    int sum = 0;
    for(int i=0; i<9; i++){
        int new_i = start_i+(sign * left_coords[i].first);
        int new_j = start_j+(sign * left_coords[i].second);
        int blow = total * percentage[i] / 100;
        sum += blow;
        if((new_i>=0 && new_j>=0) && (new_i<N && new_j<N)) arr[new_i][new_j] += blow;
    }
    int new_i = start_i+(sign * left_coords[9].first);
    int new_j = start_j+(sign * left_coords[9].second);
    if((new_i>=0 && new_j>=0) && (new_i<N && new_j<N)) arr[new_i][new_j] += (total - sum);
}

void conv_downup(vector< vector<int> > &arr, bool is_leftdown, int start_i, int start_j){
    int total = arr[start_i][start_j];
    arr[start_i][start_j] = 0;
    
    int sign = 1;
    if(!is_leftdown) sign = -1; 
    
    int sum = 0;
    for(int i=0; i<9; i++){
        int new_i = start_i+(sign * down_coords[i].first);
        int new_j = start_j+(sign * down_coords[i].second);
        int blow = total * percentage[i] / 100;
        sum += blow;
        if((new_i>=0 && new_j>=0) && (new_i<N && new_j<N)) arr[new_i][new_j] += blow;
    }
    int new_i = start_i+(sign * down_coords[9].first);
    int new_j = start_j+(sign * down_coords[9].second);
    if((new_i>=0 && new_j>=0) && (new_i<N && new_j<N)) arr[new_i][new_j] += (total - sum);
}

int main(){
    cin >> N;

    vector< vector<int> > arr(N, vector<int>(N));

    int global_total = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> arr[i][j];
            global_total += arr[i][j];
        }
    }

    pair<int, int> start = {N/2, N/2};

    int length = 1;
    bool is_leftdown = true;
    bool is_end = false;

    while(true){
        for(int i=0; i<length; i++){
            if(is_leftdown) start.second -= 1; // leftt
            else start.second += 1;          // right
            if(start.second < 0) {
                start.second = 0;
                is_end=true;
            }
            // left or right
            conv_leftright(arr, is_leftdown, start.first, start.second);
        }
        if(is_end) break;

        for(int i=0; i<length; i++){
            if(is_leftdown) start.first += 1; // down
            else start.first -= 1;          // up
            // down or up
            conv_downup(arr, is_leftdown, start.first, start.second);

        }
        is_leftdown = !is_leftdown;
        length += 1;
    }    
    
    int left = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            left += arr[i][j];
        }
    }

    cout << global_total - left;
}

기타

다른 사람의 구현코드들을 봤는데, 대부분 4방향의 상대적위치를 저장해놓고 썼다. 나같은 경우는 두가지로 나눴기 때문에
미리 저장해놓는 상대적 위치가 적었지만 함수도 2가지가 나왔는데, 4방향의 상대적위치를 저장해놓으면 함수하나만 사용할 수 있을 듯 하다.