BOJ 17143 낚시왕

www.acmicpc.net/problem/17143

17143번: 낚시왕

 

구현 문제이다.

문제가 준 대로 구현하면 되지만, 살짝의 최적화가 있어야 시간초과를 안받을 수 있다.

속도가 0 ≤ s ≤ 1000 이기 때문에 이것을 한칸한칸씩 옮겨가며 확인한다면 시간초과를 받는다 (내가 그랬다)

 

좌우로 움직이는 상어의 경우 2*(c-1) 의 주기로 위치가 반복되고, 상하로 움직이는 상어의 경우 2*(r-1)의 주기로 위치가 반복되니, 속력을 입력 받는 과정에서 처리해주어 불필요하게 위치가 반복되게 하지 않았다. 처음 제출한 코드에서 수정이 얼마 필요 없어서  이 방법을 적용하기로 했다.

(물론 방향, 속력, 현재 위치가 주어졌을때, 움직이고 난 뒤 방향과 위치를 계산할 수 도 있다.)

나의 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using std::vector;

struct{
  int r,c,s,d,z,valid;
}typedef shark;


int dr[4] = {-1,1,0,0};
int dc[4] = {0,0,1,-1};
int dd[4] = {1,0,3,2};
int arr[100][100];
vector<shark> sharks;

bool cmp(const shark a, const shark b){
  return a.z < b.z;
}

int main(){

  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  int r, c, m; 
  memset(arr, -1, sizeof arr);

  std::cin >> r >> c >> m;
  int v,w,x,y,z;
  int answer = 0;
  for(int i=0;i<m;i++){
    std::cin >> v >> w >> x >> y >> z;
    if(y >= 3)
        sharks.push_back({v-1,w-1,x%(2*(c-1)),y-1,z,1});
    else
        sharks.push_back({v-1,w-1,x%(2*(r-1)),y-1,z,1});
  }
  sort(sharks.begin(), sharks.end(), cmp);

  for(int i=0;i<sharks.size(); i++){
    shark& s = sharks[i];
    arr[s.r][s.c] = i;
  }

  for(int T=0;T<c;T++){
    //catch shark

    for(int i=0;i<r;i++){
      if(arr[i][T]!=-1){
        sharks[arr[i][T]].valid = 0;
        answer += sharks[arr[i][T]].z;
        arr[i][T]=-1;
        break;
      }
    }
    //move sharks
    for(int si=0; si < sharks.size();si++){
      shark& s = sharks[si];
      if(s.valid == 0) continue;
      if(arr[s.r][s.c]== si)
        arr[s.r][s.c] = -1;
      for(int i=0;i<s.s;i++){

        if(s.r + dr[s.d] >= r || s.r + dr[s.d] < 0){
          s.d = dd[s.d];
        }
        if(s.c + dc[s.d] >= c|| s.c + dc[s.d] < 0){
          s.d = dd[s.d];
        }
        s.r += dr[s.d];
        s.c += dc[s.d];
      }
      if(arr[s.r][s.c] < si){
        sharks[arr[s.r][s.c]].valid = 0;
      }
      arr[s.r][s.c] = si;
    }
  }

  std::cout << answer ;

  return 0;
}