낚시왕

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 0350 ~ 0520
int dx[4] = {0, 0, 1, -1}; // 위 아래 오른쪽 왼쪽
int dy[4] = {-1, 1, 0, 0};
// {{s,d},z}
pair<pair<int,int>,int> board[105][105];
pair<pair<int,int>,int> tmp[105][105];
queue<pair<int,int>> shark;
int R,C,M,ans;
int reverseDir(int n){
    if(n == 0) return 1;
    if(n == 1) return 0;
    if(n == 2) return 3;
    if(n == 3) return 2;
    return 5;
}
bool checkPos(int y, int x){
    if(x<0 or y<0 or x>=C or y>=R) return false;
    return true;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> R >> C >> M;
    for(int i=0;i<M;i++)
    {
        int r,c,s,d,z;
        cin >> r >> c >> s >> d >> z;
        board[r-1][c-1] = {{s,d-1},z};
        shark.push({r-1,c-1});
    }
    for(int cur_pos=0;cur_pos<C;cur_pos++)
    {
        pair<int,int> deletPos={1e9,1e9};
        /* 현재 열 중 가장 가까운 상어 잡기 */
        for(int j=0;j<R;j++)
            if(board[j][cur_pos].second != 0)
            {
                ans += board[j][cur_pos].second;
                board[j][cur_pos] = {{0,0},0};
                deletPos = {j,cur_pos};
                break;
            }
        /* 상어 이동 */
        int len = shark.size();
        while(len--)
        {
            auto cur = shark.front(); shark.pop();
            /* 앞에서 잡힌 상어는 건너 뛰기 */
            if(deletPos.first == cur.first and deletPos.second == cur.second) continue;
            int speed = board[cur.first][cur.second].first.first;
            int dir = board[cur.first][cur.second].first.second;
            int ny=cur.first, nx=cur.second;
            // speed에서 시간복잡도가 O(N^3)이기 때문에 줄여야함
            if(dir == 0 or dir == 1){
                speed = speed%(R*2-2);
            }else{
                speed = speed%(C*2-2);
            }
            while(speed > 0)
            {
                speed--;
                ny = ny + dy[dir];
                nx = nx + dx[dir];
                if(!checkPos(ny,nx)){
                    dir = reverseDir(dir);
                    /* 바뀐 방향 수정 */
                    board[cur.first][cur.second].first.second = dir;
                    ny = ny + dy[dir] + dy[dir];
                    nx = nx + dx[dir] + dx[dir];
                }
            }
            /* 상어의 위치가 겹칠 경우 */
            int curSize = tmp[ny][nx].second;
            int nextSize = board[cur.first][cur.second].second;
            if(curSize < nextSize)
                tmp[ny][nx] = board[cur.first][cur.second];
        }
        /* board에 복사 */
        for(int a=0;a<R;a++)
        {
            for(int b=0;b<C;b++)
            {
                board[a][b] = tmp[a][b];
                tmp[a][b] = {{0,0},0};
                if(board[a][b].second != 0)
                    shark.push({a,b});
            }
        }
    }
    cout << ans;
    return 0;
}

• 핵심
  : 시간복잡도 줄이기
  1) 이동해야하는 상어를 queue를 통해서 관리하였고, size를 통해 이번 차례 상어까지만 수행함
  2) speed에 따라 상어가 움직이는 과정에서 speed가 최대 1,000이라는 숫자를 가져서 시간초과가 날 확률이 크다
  --> speed를 방향에 따라 R과 C로 나눠서 제자리로 오는 경우만큼 줄일 수 있음