[백준] 17143번 낚시왕

17143번 낚시왕

---

1. 이해하기

• 격자판의 각 칸에는 상어가 최대 한 마리 들어있을 수 있다.
• 1초 동안 일어나는 일은 다음과 같다.
  1. 낚시왕이 오른쪽으로 한 칸 이동한다.
  2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
  3. 상어가 이동한다.
• 상어가 이동하려고 하는 칸이 격자판의 경계인 경우에는 방향을 반대로 바꿔서 이동한다.
• 상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 때, 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

---

2. 구현하기

• 이 문제의 핵심 포인트는 상어의 움직임이다.

  • 상어가 움직여서 원래 있던 자리까지 오는데의 거리는 가로 방향으로 움직였다면 2(R-1), 세로 방향으로 움직였다면 2*(C-1)이다.
  • 이를 이용해서 상어가 얼마만큼만 더 움직이면 되는지 구할 수 있다.
  • 즉, (상어의 스피드)%(원래 있던 자리까지 오는데의 거리)로 구할 수 있는 것이다.

• 이를 이용하여 상어의 다음 위치를 구현한다.

  void shark_move() {
      memset(map,-1,sizeof(map));
      for(int i = 0; i < M; i++) {
          if(shark[i].speed == -1) continue;
          int div = (shark[i].dir == 1 or shark[i].dir == 2) ? 2*(R-1) : 2*(C-1);
          int speed = shark[i].speed%div;
  
          for(int j = 0; j < speed; j++) {
              if(shark[i].dir == 1 and shark[i].x == 0) shark[i].dir = 2;
              else if(shark[i].dir == 2 and shark[i].x == R-1) shark[i].dir = 1;
              else if(shark[i].dir == 3 and shark[i].y == C-1) shark[i].dir = 4;
              else if(shark[i].dir == 4 and shark[i].y == 0) shark[i].dir = 3;
              shark[i].x+=dx[shark[i].dir]; shark[i].y+=dy[shark[i].dir];
          }
          if(map[shark[i].x][shark[i].y] == -1) map[shark[i].x][shark[i].y] = i;
          else {
              int idx = map[shark[i].x][shark[i].y];
              if(shark[i].size > shark[idx].size) {
                  shark[idx].speed = -1;
                  map[shark[i].x][shark[i].y] = i;
              } else {
                  shark[i].speed = -1;
              }
          }
      }
  }

• 낚시왕이 있는 자리에서 상어를 잡는다.

  int fishing(int c) {
      int ret = 0;
      for(int i = 0; i < R; i++) {
          if(map[i][c] != -1) {
              ret += shark[map[i][c]].size;
              shark[map[i][c]].speed = -1;
              break;
          }
      }
      return ret;
  }

• 낚시왕이 열의 끝까지 이동할 동안 상어를 잡고, 남아 있는 상어를 움직인다.

  int simulate() {
      int ret = 0;
      for(int i = 0; i < C; i++) {
          ret += fishing(i);
          shark_move();
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <cstring>
using namespace std;
struct Shark{
    int x,y,speed,dir,size;
}shark[10002];
int map[100][100];
int dx[] = {0,-1,1,0,0};
int dy[] = {0,0,0,1,-1};
int R,C,M;

void shark_move() {
    memset(map,-1,sizeof(map));
    for(int i = 0; i < M; i++) {
        if(shark[i].speed == -1) continue;
        int div = (shark[i].dir == 1 or shark[i].dir == 2) ? 2*(R-1) : 2*(C-1);
        int speed = shark[i].speed%div;

        for(int j = 0; j < speed; j++) {
            if(shark[i].dir == 1 and shark[i].x == 0) shark[i].dir = 2;
            else if(shark[i].dir == 2 and shark[i].x == R-1) shark[i].dir = 1;
            else if(shark[i].dir == 3 and shark[i].y == C-1) shark[i].dir = 4;
            else if(shark[i].dir == 4 and shark[i].y == 0) shark[i].dir = 3;
            shark[i].x+=dx[shark[i].dir]; shark[i].y+=dy[shark[i].dir];
        }
        if(map[shark[i].x][shark[i].y] == -1) map[shark[i].x][shark[i].y] = i;
        else {
            int idx = map[shark[i].x][shark[i].y];
            if(shark[i].size > shark[idx].size) {
                shark[idx].speed = -1;
                map[shark[i].x][shark[i].y] = i;
            } else {
                shark[i].speed = -1;
            }
        }
    }
}

int fishing(int c) {
    int ret = 0;
    for(int i = 0; i < R; i++) {
        if(map[i][c] != -1) {
            ret += shark[map[i][c]].size;
            shark[map[i][c]].speed = -1;
            break;
        }
    }
    return ret;
}

int simulate() {
    int ret = 0;
    for(int i = 0; i < C; i++) {
        ret += fishing(i);
        shark_move();
    }
    return ret;
}

void input() {
    memset(map,-1,sizeof(map));
    cin >> R >> C >> M;
    for(int i = 0; i < M; i++) {
        cin >> shark[i].x >> shark[i].y >> shark[i].speed >> shark[i].dir >> shark[i].size;
        shark[i].x--; shark[i].y--;
        map[shark[i].x][shark[i].y] = i;
    }
}

int main() {
    input();
    cout << simulate() << '\n';

    return 0;
}