[백준 17143] 낚시왕

 

 

 조금 타이트한 구현 문제다. 낚시 처리나, 상어끼리 잡아먹는 처리, 로직 흐름 등은 금방 떠올릴 수 있는데, 상어의 다음 위치를 구해내는 계산을 섬세하게 작성하지 않으면 틀리기 쉽다.

 

 전체적인 로직의 흐름은 간단한데, 나는 우선순위 큐를 이용했다. 낚시꾼이 열을 하나씩 이동하며 상어를 낚아야하므로, 각 열 별로 상어 인스턴스를 담아둘 우선순위 큐를 만든다. 상어의 우선순위는 더 높은 행에 위치한 상어일수록 높고, 같은 행에 있다면 크기가 클수록 우선순위가 높게 한다. 이렇게 하면, 낚시꾼에게 낚아 올려질 상어를 찾아내는 것도 쉽고, 같은 칸에 위치한 상어 중에서 가장 큰 상어가 다른 상어를 잡아먹도록 하기도 편하다.

 낚시꾼의 위치를 기준으로 반복문을 돌리는데, 그 안에서 상어 처리를 위해 모든 우선순위 큐 리스트에 대해 반복문을 돌린다. 만약 열에 상어가 있다면, 해당 우선순위 큐가 빌 때까지 상어 처리를 시작한다. 같은 행에 상어가 있다면 모두 pop해서 잡아먹은 것으로 처리하고, 탐색 중인 열이 낚시꾼이 있는 열이라면 낚시 처리도 해준다. 상어가 낚시를 당하는 경우가 아니라면, 상어의 정보를 바탕으로 다음 위치를 찾아 새로운 우선순위 큐 리스트에 넣어준다.

 

 상어의 이동은 결국 인덱스가 커졌다 작아졌다하는 사이클을 반복하며 나타나기 때문에, 나는 각 이동 방향별 사이클을 가지고 다음 위치를 계산해주었다. 지금 생각해보면, 조금 신경써서 만들면 방향이 위, 아래인 경우와 오른쪽, 왼쪽인 경우를 묶어서 처리할 수도 있었을 것 같다.

 

 위의 과정들을 모든 열의 우선순위 큐에 대해 처리해주고 나면, 1초 뒤의 상어 위치에 해당하는 새로운 우선순위 큐 리스트가 완성되게 된다. 낚시꾼이 끝까지 이동하고 나면, 낚은 물고기의 크기 총합을 출력하고 종료하면 된다.

 대부분의 시간을 다음 위치 계산하는 부분 수정하느라 쓴 것 같다..

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

class Shark {
public: 
    int r, c, s, d, z;

    Shark(int r, int c, int s, int d, int z) {
        this->r = r;
        this->c = c;
        this->s = s;
        this->d = d;
        this->z = z;
    }

    bool operator < (const Shark& obj) const {
        if(this->r == obj.r) return this->z < obj.z;
        return this->r > obj.r;        
    }
};

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

    int r, c, m;
    int sharkR, sharkC, s, d, z;
    cin >> r >> c >> m;

    vector<priority_queue<Shark> > pqByRowList(c+1);

    for(int i=0; i<m; i++) {
        cin >> sharkR >> sharkC >> s >> d >> z;
        pqByRowList[sharkC].push(
            Shark(
                sharkR, sharkC, s, d, z
            )
        );
    }

    int result = 0;
    int rCycle = r*2-2;
    int cCycle = c*2-2;
    for(int i=1; i<=c; i++) {
        bool acquireFlag = false;
        
        vector<priority_queue<Shark> > newPqRowList(c+1); //이동 후 상어 리스트

        for(int j=1; j<=c; j++) { //상어 처리
            while(!pqByRowList[j].empty()) { //열에 상어 있는 경우
                auto target = pqByRowList[j].top(); 
                pqByRowList[j].pop();
                while(!pqByRowList[j].empty() && pqByRowList[j].top().r == target.r) { //같은 행 잔여 상어 있으면 잡아먹는 처리
                    pqByRowList[j].pop();
                }
                if(!acquireFlag && i==j) {
                    result+=target.z;
                    acquireFlag = true;
                    continue;
                }
                
                switch(target.d) {
                    case 1: {
                        int order = (target.s + r - target.r) % rCycle;
                        if(order>rCycle/2) {
                            newPqRowList[target.c].push(Shark(
                                order-rCycle/2+1, target.c, target.s, 2, target.z
                            )); 
                        } else {
                            newPqRowList[target.c].push(Shark(
                                r-order, target.c, target.s, 1, target.z
                            )); 
                        } 
                        break;
                    }
                    case 2: {
                        int order = (target.s + target.r - 1) % rCycle;
                        if(order>rCycle/2) {
                            newPqRowList[target.c].push(Shark(
                                r-(order-rCycle/2), target.c, target.s, 1, target.z
                            )); 
                        } else {
                            newPqRowList[target.c].push(Shark(
                                order+1, target.c, target.s, 2, target.z
                            )); 
                        } 
                        break;
                    }
                    case 3: {
                        int order = (target.s + target.c - 1) % cCycle;
                        if(order>cCycle/2) {
                            newPqRowList[c-(order-cCycle/2)].push(Shark(
                                target.r, c-(order-cCycle/2), target.s, 4, target.z
                            )); 
                        } else {
                            newPqRowList[order+1].push(Shark(
                                target.r, order+1, target.s, 3, target.z
                            )); 
                        } 
                        break;
                    }
                    case 4: {
                        int order = (target.s + c - target.c) % cCycle;
                        if(order>cCycle/2) {
                            newPqRowList[order-cCycle/2+1].push(Shark(
                                target.r, order-cCycle/2+1, target.s, 3, target.z
                            )); 
                        } else {
                            newPqRowList[c-order].push(Shark(
                                target.r, c-order, target.s, 4, target.z
                            )); 
                        } 
                        break;
                    }
                }
            }
                        
        }
        
        pqByRowList = newPqRowList;
    }

    cout << result;
}