[백준 17143] 낚시왕 (C++)

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

- 입력 

 첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C) 둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다. 두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다. 

 - 출력

 낚시왕이 잡은 상어 크기의 합을 출력한다. 

 - 풀이 (어려웠던 점)

 다른건 괜찮았는데, 상어를 움직일 때가 정말 난해한 문제였습니다. 또한 상어가 같은 공간에 있는 경우에 가장 크기가 큰 상어가 나머지 상어를 잡는 구조인데, 처음 생각한 것은 칸에 넣을때 마다 최신화를 해주면 되겠다 였는데, 같은 크기의 상어가 들어왔을때 저장해야 하는 문제가 생겼습니다. 또한 방향을 바꾸는 타이밍을 잘못 계산했고, 루프를 어떻게 돌려야 효율적으로 상어를 이동시킬지에 대한 부분도 깊게 생각을 했습니다. 

 - 코드

#include <iostream>
#include <vector>
#include <algorithm>
 
#define endl "\n"
 
int R, C, M;
struct shark
{
    int r,c,d,s,z;
    int live;
};
std::vector<shark> shark_location;
std::vector<std::pair<int, int> >direction;
std::vector<std::vector<int> >coord;
std::vector<std::vector<int> >sharks_save;
int ans;
 
int make_reverse_direction(shark sharks)
{
    if (sharks.d == 1)
        return(2);
    else if (sharks.d == 2)
        return(1);
    else if (sharks.d == 3)
        return(4);
    else
        return(3);
}
 
void input_faster()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
}
 
void input()
{
    input_faster();
    std::cin >> R >> C >> M;
    shark_location.resize(M+1);
    direction = {{0,0}, {-1, 0}, {1, 0}, {0, 1}, {0, -1}}; // up down right left
    coord.resize(R+1, std::vector<int>(C+1, 0));
    sharks_save.resize((R + 1)*(C + 1));
    ans = 0;
    for (size_t i = 1 ; i <= static_cast<size_t>(M) ; i++)
    {
        std::cin >> shark_location[i].r;
        std::cin >> shark_location[i].c;
        std::cin >> shark_location[i].s;
        std::cin >> shark_location[i].d;
        std::cin >> shark_location[i].z;
        shark_location[i].live = 1;
        coord[shark_location[i].r][shark_location[i].c] = i;
    }
}
 
void catch_shark(size_t index)
{
    for (size_t i = 1; i <= static_cast<size_t>(R) ; i++)
    {
        if (coord[i][index] >= 1)
        {
            shark_location[coord[i][index]].live = 0;
            ans += shark_location[coord[i][index]].z;
            break;
        }
    }
}
 
int shark_reached_max(size_t i)
{
    if (shark_location[i].d == 1 || shark_location[i].d == 2)
        return (R);
    else
        return (C);
}
 
void shark_move()
{
    for (size_t i = 1 ; i <= static_cast<size_t>(M) ; i++)
    {
        if (!shark_location[i].live)
            continue;
        int shark_can_go = shark_location[i].s;
        int max_val = shark_reached_max(i);
        int move;
 
        while (shark_can_go > 0)
        {
            move = max_val - 1;
            if (shark_location[i].d == 2)
                move = R - shark_location[i].r;
            else if (shark_location[i].d == 1)
                move = shark_location[i].r - 1;
            else if (shark_location[i].d == 4)
                move = shark_location[i].c - 1;
            else
                move = C - shark_location[i].c;
            if (shark_can_go - move < 0)
                move = shark_can_go;
            shark_can_go-= move;
            shark_location[i].r += (direction[shark_location[i].d].first * move);
            shark_location[i].c += (direction[shark_location[i].d].second * move);
            if (shark_location[i].d == 1 || shark_location[i].d == 2)
            {
                if (shark_location[i].r == 1 || shark_location[i].r == R)
                    shark_location[i].d = make_reverse_direction(shark_location[i]);
            }
            else
            {
                if (shark_location[i].c == 1 || shark_location[i].c == C)
                    shark_location[i].d = make_reverse_direction(shark_location[i]);
            }
        }
 
        int x = shark_location[i].c;
        int y = shark_location[i].r;
        if (coord[y][x]) // already shark is in
        {
            if (shark_location[coord[y][x]].z < shark_location[i].z)
            {
                for(size_t k = 0 ; k < sharks_save[y * C + x].size(); k++)
                {
                    shark_location[sharks_save[y * C + x][k]].live = 0;
                }
                sharks_save[y * C + x].clear();
                sharks_save[y * C + x].push_back(i);
                coord[y][x] = i;
            }
            else if (shark_location[coord[y][x]].z == shark_location[i].z)
            {
                sharks_save[y * C + x].push_back(i);
            }
            else
                shark_location[i].live = 0;
        }
        else
        {
            sharks_save[y * C + x].push_back(i);
            coord[y][x] = i;
        }
    }
}
 
void solve()
{
    for(size_t i = 1 ; i <= static_cast<size_t>(C); i++) // man move
    {
 
        catch_shark(i);
        std::fill(coord.begin() , coord.end(), std::vector<int>(C+1, 0)); // coord initialization
        std::fill(sharks_save.begin(), sharks_save.end(), std::vector<int>(0));
        shark_move();
    }
}
 
void print_val()
{
    std::cout << ans;
}
 
int main()
{
    input();
    solve();
    print_val();
    return (0);
}