[BOJ] 17143 : 낚시왕

문제 링크

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

17143번: 낚시왕

각 상어의 위치를 조정하는 구현 문제.

 

풀이

 낚시왕은 처음에 1번 열보다 한 칸 왼쪽에 있다. 즉 0번열에 있다고 생각하면 된다. 낚시왕은 땅에만 있기 때문에 행은 항상 0번행에 있다고 생각하면 된다. (0, 0) 에서 오른쪽으로 한 칸씩 이동하면서 낚시를 한다. 낚시왕이 한 칸 이동할 때마다 상어들도 속도에 따라 이동한다.

1. 낚시왕이 오른쪽으로 한 칸 이동한다.

 이건 그냥 낚시왕의 x좌표를 +1 해주면 된다.

2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.

 낚시왕이 있는 좌표에서 x좌표는 고정한 채 y좌표를 하나씩 늘려가며 물속으로 내려간다. 처음으로 만난 상어가 땅에서 가장 가까운 상어이다. 이 상어의 크기를 잡은 상어 크기의 합(ans)에 더해주고 이 상어는 벡터에서 삭제한다.

3. 상어가 이동한다.

 이 문제의 관건은 상어의 이동인 것 같다.

상어마다 일정한 속도를 가지고 있다. 그리고 상어가 범위를 벗어나 이동하려고하면(벽에 박으면) 방향을 바꿔서 한 칸 이동한다. 그런데 상어를 한 칸 한 칸 이동시키기에는 시간이 너무 오래걸린다.

상어의 속력은 1초 동안 상어가 "이동해야할 거리"와 같다.

이동해야할 거리(distance)가 0이 될 때까지 상어는 이동한다.

임의의 상어가 현재 오른쪽으로 이동하고있다고 가정하자. 이 상어는 오른쪽 또는 왼쪽으로만 이동하기 때문에 y좌표는 신경쓰지 않는다.

현재 이 상어가 x에 있다고 가정하면 상어가 (C - x)만큼 이동하면 오른쪽 벽에 박게된다. 남아있는 이동해야 할 거리가 (C - x) 보다 크거나 같다면 이 상어를 C(오른쪽 젤 끝)로 이동시키고 방향을 바꾼다. 이동 후 남은 거리는 원래 남아있던 이동거리 - (C - x)가 된다.

반대로 상어가 왼쪽으로 이동하고 있다면, 현재 상어의 위치가 x면 (x - 1)만큼 이동하면 왼쪽 벽에 박게된다.

남은 이동해야할 거리가 (x - 1)보다 크거나 같다면 이 상어를 1(왼쪽 젤 끝)로 이동시키고 방향을 바꾼다.

만약 이동해야할 거리를 모두 이동해도 벽에 박지않으면 상어를 남은 거리만큼 이동시킨 후, 방향을 유지한 채 이동을 종료한다.

 상어가 위아래로 움직이고 있을 때도 똑같은 방식으로 이동하면 된다. 이때는 x좌표를 고정한채 y좌표만 이동시킨다.

 모든 상어를 이동시킨 후에 한 칸에 여러마리의 상어가 있다면 이 상어들을 크기 순으로 정렬한 후 제일 큰 상어만 남기고 나머지 작은 상어들은 삭제한다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 100 + 5;
vector<pair<int, pair<int, int>>> Shark[MAX_N][MAX_N];
int R, C, M;
int ans;
 
void Catch_Shark(int st) {
    for (int i = 1; i <= R; i++) {
        if (!Shark[i][st].empty()) {
            ans += Shark[i][st][0].first;
            Shark[i][st].clear();
            return;
        }
    }
}
 
void change_direct(int &direction) {
    if (direction == 1)
        direction = 2;
    else if (direction == 2)
        direction = 1;
    else if (direction == 3)
        direction = 4;
    else if (direction == 4)
        direction = 3;
}
 
void Shark_Move() {
    vector<pair<int, pair<int, int>>> temp[MAX_N][MAX_N];
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (Shark[i][j].empty())
                continue;
            int size = Shark[i][j][0].first;
            int Pace = Shark[i][j][0].second.first;
            int distance = Pace;
            int direction = Shark[i][j][0].second.second;
            if (direction == 1 || direction == 2) {
                int now = i;
                while (distance) {
                    if (direction == 1) { //위로 가는중
                        if (distance >= (now - 1)) {
                            distance -= (now - 1);
                            now = 1;
                            change_direct(direction);
                        }
                        else {
                            now -= distance;
                            distance = 0;
                        }
                        continue;
                    }
                    else if (direction == 2) { // 내려가는 중 
                        if (distance >= R - now) {
                            distance -= (R - now);
                            now = R;
                            change_direct(direction);
                        }
                        else {
                            now += distance;
                            distance = 0;
                        }
                    }
                }
                temp[now][j].push_back({ size,{Pace, direction} });
            }
            else if (direction == 3 || direction == 4) {
                int now = j;
                while (distance) {
                    if (direction == 3) { //오른쪽으로 가는 중
                        if (distance >= (C - now)) {
                            distance -= (C - now);
                            now = C;
                            change_direct(direction);
                        }
                        else {
                            now += distance;
                            distance = 0;
                        }
                    }
                    else if (direction == 4) { //왼쪽으로 가는 중
                        if (distance >= (now - 1)) {
                            distance -= (now - 1);
                            now = 1;
                            change_direct(direction);
                        }
                        else {
                            now -= distance;
                            distance = 0;
                        }
                    }
                }
                temp[i][now].push_back({ size ,{Pace, direction} });
            }
        }
    }
 
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            Shark[i][j].clear();
            if (temp[i][j].empty()) {
                continue;
            }
            else if (temp[i][j].size() == 1) {
                Shark[i][j] = temp[i][j];
            }
            else {
                sort(temp[i][j].begin(), temp[i][j].end(), greater<pair<int,pair<int,int>>>());
                pair<int, pair<int, int>> copy = temp[i][j][0];
                Shark[i][j].push_back(copy);
            }
        }
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> R >> C >> M;
    for (int i = 0; i < M; i++) {
        int r, c, s, d, z;
        cin >> r >> c >> s >> d >> z;
        Shark[r][c].push_back({ z,{s,d} });
    }
    int Fishing_King_col = 0;
    while (Fishing_King_col <= C) {
        Fishing_King_col++;
        Catch_Shark(Fishing_King_col);
        Shark_Move();
    }
    cout << ans << "\n";
    return 0;
}