백준 17143번 낚시왕 C++ (골드1)

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

 

상어가 계속 움직이고 있는 상태에서 상어 낚시꾼이 오른쪽으로 움직이면서 잡을 수 있는 상어의 총 크기를 구하는 문제이다.

 

Shark 클래스를 만들어서 상어의 크기, 속도, 움직이는 방향 등을 저장하고 관리하기 위해 입력받은 순서대로 Id를 부여하였다.

클래스 내에 Move, Caught 멤버함수를 구현하여 상어가 움직이거나 잡혔을때 행동을 작성하였다.

 

1. 낚시꾼이 움직인다.

2. 낚시꾼이 있는 열에서 땅에서 가장 가까운 상어를 잡는다.

3. 상어가 움직인다.

 

위의 순서대로 동작한다.

 

낚시터의 격자에 상어의 Id로 상어의 위치를 표시했고, 낚시꾼이 움직이다가 상어를 잡을 수 있는 상황이면 Id로 상어의 정보를 찾아서 Shark::Caught함수를 실행하면 상어의 크기를 반환해주고 해당 상어의 정보를 날려준다.

 

상어의 움직임은 Shark::Move함수로 구현했고, 일단 현재 위치에 있는 상어의 Id가 내 Id라면 해당 위치의 Id를 -1로 밀어준다. (다른 상어가 먼저 움직여서 현재 위치에 있을수도 있기 때문에)

그리고 방향, 속도 정보를 이용하여 이동시켜주고 새로운 위치에 내 Id를 기록한다.

 

움직인 뒤 같은 위치에 상어가 있다면 크기가 큰 상어가 다른 상어를 모두 잡아먹기 때문에 이동한 후의 위치를 Key로 갖고 상어의 Id를 Value로 갖는 map을 만들어서 map에 정보를 기록하는데, 만약 이미 해당 key가 존재한다면 이미 해당 위치에 다른 상어가 도착한 상태이다.

그렇기 때문에 크기 비교를 하여 하나의 상어를 없애주어야 한다.

전에 존재하던 상어의 id인 value와 현재 상어의 id 정보를 이용해 상어의 정보를 가져와서 크기를 비교하고 크기가 작은 상어를 없애준다.

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

class Shark;

int R, C, m;
int dRow[4] = { -1,1,0,0 };
int dCol[4] = { 0,0,1,-1 };
vector<vector<int>> board;
unordered_map<int, Shark*> sharks;

class Shark 
{
public:
    Shark(int id, int r, int c, int s, int d, int z) : id(id), r(r), c(c), s(s), d(d), z(z)
    {
        board[r][c] = id;
    }

public:
    void Move() {
        if (board[r][c] == id)
            board[r][c] = -1;
        int moveDist = s;
        while (moveDist > 0)
        {
            int remainDist;
            if (d == 0){
                remainDist = r - 1;
            }
            else if (d == 1){
                remainDist = R - r;
            }
            else if (d == 2){
                remainDist = C - c;
            }
            else{
                remainDist = c - 1;
            }

            if (remainDist <= moveDist){
                r += dRow[d] * remainDist;
                c += dCol[d] * remainDist;
                moveDist -= remainDist;
                if (d == 0) d = 1;
                else if (d == 1) d = 0;
                else if (d == 2) d = 3;
                else if (d == 3) d = 2;
            }
            else {
                r += dRow[d] * moveDist;
                c += dCol[d] * moveDist;
                moveDist = 0;
            }
        }
        board[r][c] = id;
    }
    
    int Caught() {
        board[r][c] = -1;
        sharks.erase(id);
        return z;
    }

public:
    int id;
    int r;
    int c;
    int s;
    int d;
    int z;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> R >> C >> m;
    board = vector<vector<int>>(R + 1, vector<int>(C + 1, -1));
    for (int i = 0; i < m; i++)
    {
        int id = i;
        int r, c, s, d, z;
        cin >> r >> c >> s >> d >> z;
        d--;
        Shark* shark = new Shark(id, r, c, s, d, z);
        sharks.insert({ id, shark });
    }
    int ans = 0;
    for (int c = 1; c <= C; c++)
    {
        // 상어잡기
        for (int r = 1; r <= R; r++)
        {
            if (board[r][c] != -1)
            {
                int id = board[r][c];
                Shark* shark = sharks.find(id)->second;
                ans += shark->Caught();
                break;
            }
        }

        // 상어 이동
        map<pair<int, int>, int> posCheck;
        vector<int> deleteSharks;
        for (auto a : sharks) {
            a.second->Move();
            pair<int, int> pos = { a.second->r, a.second->c };
            int id = a.second->id;
            auto it = posCheck.find(pos);

            // 해당 위치에 아무도 없음, 그냥 추가
            if (it == posCheck.end())
            {
                posCheck.insert({ pos,id });
            }
            else { // 이미 누가 있음, 크기가 작은 상어는 삭제 예약 목록에 등록
                int lastSharkId = it->second;
                Shark* currShark = sharks.find(id)->second;
                Shark* lastShark = sharks.find(lastSharkId)->second;
                if (currShark->z < lastShark->z)
                {
                    deleteSharks.push_back(id);
                    board[lastShark->r][lastShark->c] = lastSharkId;
                }
                else {
                    it->second = id;
                    deleteSharks.push_back(lastSharkId);
                }
            }
        }
        for (auto id : deleteSharks)
        {
            sharks.erase(id);
        }
    }
    cout << ans;
}