[C++] 백준 | 17143번 낚시왕

17143번: 낚시왕

문제에 적힌 순서대로 구현했다.

 

1. 낚시왕을 옮기고, 같은 열의 상어를 잡는다.

2. 상어를 옮기고, 그 상어의 위치를 임시로 저장한다. 나는 arr에 저장했다.

3. 옮긴 상어의 위치에 다른 상어가 있다면, 큰 상어만 남긴다.

4. 이동이 끝나면 arr에 임시로 저장돼있는 상어를 전부 map에 다시 옮겨준다.

 

위의 과정을 낚시왕이 1열에서 c열까지 이동할 때까지

즉, c번 반복하며 최종 점수를 출력하면 된다.

 

상어의 최대 속력은 1000으로, 나와 같이 while 문으로 모든 상어를 천 번씩 옮기면 TLE를 받는다.

따라서 모듈러 연산을 통해 양 벽을 부딪힌 후,

상어가 같은 방향, 같은 위치로 돌아올 경우에서부터 계산을 해주면 된다.

 

구현 문제인데, 문제가 친절하고 자세하게 설명돼있어 골드 1 문제같지는 않았다.

큰 상어만 남기는 아이디어가 힘들긴 했다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Shark {
    int R, C, speed, dir, sco;
};
vector<Shark> map[101][101];
vector<Shark> arr[101][101];
int dx[5] = {0, -1, 1, 1, -1}, score;

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int r,c,m;
    cin>>r>>c>>m;
    for(int i = 0; i < m; i++) {
        struct Shark a;
        cin>>a.R>>a.C>>a.speed>>a.dir>>a.sco;
        if(a.dir == 1 || a.dir == 2) a.speed %= (r - 1) * 2;
        else a.speed %= (c - 1) * 2;
        map[a.R][a.C].push_back(a);
    }
    
    int fisher = 0, coun = c;
    while(coun--) {
        fisher++; //낚시왕 옮기기
        for(int i = 1; i <= r; i++) { //상어 잡기
            if(map[i][fisher].empty()) continue;
            score += map[i][fisher][0].sco;
            map[i][fisher].pop_back();
            break;
        }
        
        for(int i = 1; i <= r; i++) { //상어가 있다면 옮겨주기
            for(int j = 1; j <= c; j++) {
                if(map[i][j].empty()) continue;
                struct Shark t = map[i][j][0];
                int move = t.speed;
                if(t.dir == 1 || t.dir == 2) {
                    while(move--) {
                        if(t.R == 1) t.dir = 2;
                        if(t.R == r) t.dir = 1;
                        t.R += dx[t.dir];
                    }
                }
                else {
                    while(move--) {
                        if(t.C == 1) t.dir = 3;
                        if(t.C == c) t.dir = 4;
                        t.C += dx[t.dir];
                    }
                }
                
                if(arr[t.R][t.C].empty()) {//큰 상어만 남기기
                    arr[t.R][t.C].push_back(t);
                }
                else {
                    if(arr[t.R][t.C][0].sco < t.sco) {
                        arr[t.R][t.C].pop_back();
                        arr[t.R][t.C].push_back(t);
                    }
                }
            }
        }
        
        for(int i = 1; i <= r; i++) { //업데이트
            for(int j = 1; j <= c; j++) {
                map[i][j] = arr[i][j];
                if(!arr[i][j].empty()) arr[i][j].pop_back();
            }
        }
    }
    cout<<score;
}