[백준 c++] 17143 낚시왕

문제

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

낚시왕이 무려 상어 낚시를 하려고 한다.
낚시왕은 오른쪽으로 한 칸씩 이동하며 서있는 줄에서 가장 가까운 상어를 잡을 수 있다.
각자 속력, 이동 방향, 크기를 가지고 있는 상어가 RxC격자판 위에서 1초마다 움직일 때 두 마리 이상의 상어가 같은 칸에 들어가면 더 큰 상어가 나머지를 잡아먹는다.

낚시왕이 잡은 상어 크기 합을 구하라.

풀이

1. struct a[10001]: struct 이용하여 상어 정보 저장하는 상어 고유 번호를 idx로하는 배열. death라는 항목을 추가해서 죽었는지 살았는지 체크하는 flag로 사용했다.

2. _map[101][101]: 상어 위치 현황

3. 속력에 따른 상어 왕복 횟수 줄이기⭐️

4. temp에는 위치 이동을 끝낸 상어를 저장하는데, 같은 위치에 또 상어가 오면 크기 비교를 해준다.

5. 상어 이동 모두 끝나면 temp값을 map으로 카피한다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
struct Shark{
    int x, y, s, z, dir, death;
} a[10001];
int _map[101][101], R, C, M, res, temp[101][101];
int dx[] = {0, 0, 0, 1, -1}, dy[] = {0, -1, 1, 0, 0};
int main()
{
    cin >> R >> C >> M;
    for (int i = 1; i <= M; i++)
    {
        cin >> a[i].y >> a[i].x >> a[i].s >> a[i].dir >> a[i].z;
        a[i].y -= 1;
        a[i].x -= 1;
        _map[a[i].y][a[i].x] = i;
    }
    for (int t = 0; t < C; t++) // x
    {
        for (int i = 0; i < R; i++) // y
        {
            if (_map[i][t])
            {
                a[_map[i][t]].death = 1;
                res += a[_map[i][t]].z;
                _map[i][t] = 0;
                break;
            }
        }
        fill(&temp[0][0], &temp[0][0] + 101 * 101, 0);
        for (int i = 1; i <= M; i++)
        {
            if (a[i].death)
                continue;
            int _y = a[i].y;
            int _x = a[i].x;
            int s = a[i].s;
            int d = a[i].dir;
            int ny, nx;
            while (1)
            {
                ny = _y + s * dy[d];
                nx = _x + s * dx[d];
                if (ny >= 0 && nx >= 0 && ny < R && nx < C)
                    break;
                else if (d == 1 && ny < 0)
                    s -= _y, _y = 0, d = 2;
                else if (d == 2 && ny >= R)
                    s -= R - 1 - _y, _y = R - 1, d = 1;
                else if (d == 3 && nx >= C)
                    s -= C - 1 - _x, _x = C - 1, d = 4;
                else if (d == 4 && nx < 0)
                    s -= _x, _x = 0, d = 3;
            }
            if (temp[ny][nx])
            {
                if (a[temp[ny][nx]].z < a[i].z)
                {
                    a[temp[ny][nx]].death = 1;
                    temp[ny][nx] = i;
                }
                else
                    a[i].death = 1;
            }
            else
                temp[ny][nx] = i;
            a[i].x = nx, a[i].y = ny, a[i].dir = d;
        }
        for (int y = 0; y < R; y++)
        {
            for (int x = 0; x < C; x++)
                _map[y][x] = temp[y][x];
        }
    }

    cout << res << "\n";
    return 0;
}