[삼성SW테스트] 백준 17143번 - 낚시왕

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

17143번: 낚시왕

삼성 SW 테스트 (19년 상반기) 시뮬레이션 문제다.

주어진 조건에 대해 시간 제한 (1초)을 오버해 처음엔 틀렸지만 

상어의 이동 속도에 대해 전부 루프를 돌지 않고 규칙을 찾아 방향과 위치가 같은 상태로 돌아오는데 이동한 거리를 통해 시간을 줄일 수 있었다.

 

(추가)
시간 복잡도를 증가시키지 않기 위해 R x C를 돌고 그 안에서 필요한 상어정보들만 뽑아 큐에 넣어 R x C x 무언가가 되어 시간복잡도를 증가시키는 코딩은 좋지 않다. 즉 R x C 루프에서 정보를 뽑고 그 후에 C x M x S 시간복잡도를 별도로 갖게 된다면 실행시간을 단축시킬 수 있다. 앞으로도 거대루프 안에서 계속 무언가를 코딩한다기 보다는 그 안에서 필요한 정보를 별도의 자료구조에 저장하고, 이를 활용하여 해답을 도출하는 습관을 갖도록 하자.

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#define maxlen 101
using namespace std;
 
int R, C, M;
int r, c, s, d, z;
int answer = 0;
typedef struct shark{
    int size;
    int speed;
    int direction;
}shark;
vector<shark> Sharks[maxlen][maxlen];
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> R >> C >> M;
    for (int i = 0; i < M; i++){
        cin >> r >> c >> s >> d >> z;
        shark aShark;
        aShark.size = z;
        aShark.direction = d;
        aShark.speed = s;
        Sharks[r][c].push_back(aShark);
    }
    int curPos = 0;
    curPos++;
    while (curPos <= C){
        // catch
        for (int row = 1; row <= R; row++){
            if (Sharks[row][curPos].size()){
                answer += Sharks[row][curPos][0].size;
                Sharks[row][curPos].clear();
                break;
            }
        }
        // move
        queue<pair<pair<int, int>, pair<int, pair<int, int> > > > q;
        for (int row = 1; row <= R; row++){
            for (int col = 1; col <= C; col++){
                if (Sharks[row][col].size()){
                    q.push(make_pair(make_pair(row, col), make_pair(Sharks[row][col][0].size, make_pair(Sharks[row][col][0].speed, Sharks[row][col][0].direction))));
                    Sharks[row][col].clear();
                }
            }
        }
        while (!q.empty()){
            int row = q.front().first.first;
            int col = q.front().first.second;
            int size = q.front().second.first;
            int speed = q.front().second.second.first;
            int direction = q.front().second.second.second;
            q.pop();
            int howmanymove;
            if (direction == 1 || direction == 2){
                howmanymove = speed % (2 * (R - 1));
            }
            else
                howmanymove = speed % (2 * (C - 1));
            for (int i = 0; i < howmanymove; i++){
                if (direction == 1){
                    //up
                    if (row == 1){
                        direction = 2;
                        row++;
                    }
                    else
                        row--;
                }
                else if (direction == 2){
                    if (row == R){
                        direction = 1;
                        row--;
                    }
                    else
                        row++;
                }
                else if (direction == 3){
                    if (col == C){
                        col--;
                        direction = 4;
                    }
                    else{
                        col++;
                    }
                }
                else{
                    if (col == 1){
                        col++;
                        direction = 3;
                    }
                    else
                        col--;
                }
            }
            if (Sharks[row][col].size() != 0){
                // 기존에 있으면 크기비교해서 넣어주기.
                if (Sharks[row][col][0].size < size){
                    Sharks[row][col][0].size = size;
                    Sharks[row][col][0].speed = speed;
                    Sharks[row][col][0].direction = direction;
                }
            }
            else{
                shark aShark;
                aShark.size = size;
                aShark.speed = speed;
                aShark.direction = direction;
                Sharks[row][col].push_back(aShark);
            }
        }
        curPos++;
    }
    cout << answer << '\n';
    return 0;
}