BOJ 17143, 낚시왕

Source: BOJ 17143 낚시왕

개인적으로 꽤나 어려웠던 문제였다.
처음에는 shark라는 구조체를 정의하고 각각의 상어를 움직이려고 했으나 보드판 자체를 shark 구조체 형식으로 나타내는 것이 더 효율적이라고 판단하여 문제를 다시 풀게 되었다.

---

일단 문제를 정리해보면

1. 보드판에 상어가 있고 각 상어는 위치, 속력, 방향, 크기를 갖고 있다.
2. 낚시꾼이 1 열씩 이동하면서 땅과 가장 가까운 상어를 잡는다.
3. 낚시꾼의 이동 후 상어는 각자의 속력과 방향에 따라 이동한다
4. 이동을 마친 후 같은 칸에 있는 상어는 크기가 가장 큰 상어만 남는다.
5. 반복..

---

PS LOGIC

1. shark라는 구조체 정의 (속도, 방향, 크기)
2. 보드판(board[][])을 shark라는 구조체로 만듬
3. 보드(board[][])에 shark를 표시
4. board1[][]을 만들고 move함수를 통해 1초 후 상어의 새로운 위치를 board1에 저장
5. board에 board1을 복사
6. board1 초기화

---

//낚시꾼이 오른쪽으로 한칸이동
//낚시꾼이 있는 열 중 땅과 가장 가까운 상어 잡음. 잡은 상어 사라짐
//상어 이동
//한칸에 상어가 두마리 이상일 때 큰상어가 작은상어를 잡아먹음.

//상어는 rcsdz로 표시 -> r,c: 위치/ s: 속력/ d: 이동방향 / z: 크기
//d: 1, 2, 3, 4 -> 위, 아래, 우, 좌
#include <bits/stdc++.h>
using namespace std;

int dx[] = {0, -1, 1, 0, 0};
int dy[] = {0, 0, 0, 1, -1};
struct shark{
  int speed;
  int dir;
  int size;
};
shark board[102][102];
shark board1[102][102];
int R,C,M;

void move(){
  for(int i=1; i<=R; i++){
    for(int j=1; j<=C; j++){
      board1[i][j].size = 0;
      board1[i][j].speed = 0;
      board1[i][j].dir = 0;
    }
  }
  int mod_R = (R*2)-2;
  int mod_C = (C*2)-2;
  for(int i=1; i<=R; i++){
    for(int j=1; j<=C; j++){
      auto cur = board[i][j];
      if(cur.size>0){
        if(cur.dir == 1 ||cur.dir == 2){
          cur.speed %= mod_R;
          int curx = i;
          int cury = j;
          while(cur.speed--){
            int nx = curx + dx[cur.dir];
            int ny = cury + dy[cur.dir];
            if(nx<1||ny<1||nx>R||ny>C){
              cur.dir = 3-cur.dir;
              nx = curx + dx[cur.dir];
              ny = cury + dy[cur.dir];
            }
            curx = nx; cury = ny;
          }
          board[i][j].dir = cur.dir;
          if(board1[curx][cury].size> board[i][j].size) continue;
          board1[curx][cury] = board[i][j];
        }
        else if(cur.dir == 3 || cur.dir == 4){
          cur.speed %= mod_C;
          int curx = i;
          int cury = j;
          while(cur.speed--){
            int nx = curx + dx[cur.dir];
            int ny = cury + dy[cur.dir];
            if(nx<1||ny<1||nx>R||ny>C){
              cur.dir = 7-cur.dir;
              nx = curx + dx[cur.dir];
              ny = cury + dy[cur.dir];
            }
            curx = nx; cury = ny;
          }
          board[i][j].dir = cur.dir;
          if(board1[curx][cury].size> board[i][j].size) continue;
          board1[curx][cury] = board[i][j];
        }
      }
    }
  }
  for(int i=1; i<=R; i++){
    for(int j=1; j<=C; j++){
      board[i][j] = board1[i][j];
    }
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin>>R>>C>>M;
  for(int i=1; i<=R; i++){
    for(int j=1; j<=C; j++){
      board[i][j].speed = 0;
      board[i][j].dir = 0;
      board[i][j].size = 0;
    }
  }
  while(M--){
    int r,c,s,d,z;
    cin>>r>>c>>s>>d>>z;
    board[r][c].speed = s;
    board[r][c].dir = d;
    board[r][c].size = z;
  }

  int king = 0;
  int ans = 0;
  while(king<=C){
    king++;
    for(int i=1; i<=R; i++){
      if(board[i][king].size>0){
        ans+=board[i][king].size; 
        board[i][king].size=0;
        board[i][king].dir=0;
        board[i][king].speed=0;
        break;}
    }
    move();
  }
  cout<<ans;
}