[ALGORITHM]BOJ17143-낚시왕

문제

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.

낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.

낚시왕이 오른쪽으로 한 칸 이동한다.
낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
상어가 이동한다.

상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.

왼쪽 그림의 상태에서 1초가 지나면 오른쪽 상태가 된다. 상어가 보고 있는 방향이 속도의 방향, 왼쪽 아래에 적힌 정수는 속력이다. 왼쪽 위에 상어를 구분하기 위해 문자를 적었다.

상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.

입력

첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)

둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.

두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

출력

낚시왕이 잡은 상어 크기의 합을 출력한다.

예제 입력 1

예제 출력 1

각 칸의 왼쪽 아래에 적힌 수는 속력, 오른쪽 아래는 크기, 왼쪽 위는 상어를 구분하기 위한 문자이다. 오른쪽 위에 ❤️는 낚시왕이 잡은 물고기 표시이다.

초기 상태

1초

2초 (E번 상어는 B번에게 먹혔다)

3초

4초

5초

6초

예제 입력 2

100 100 0

예제 출력 2

예제 입력 3

예제 출력 3

예제 입력 4

예제 출력 4

나의 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int R;
    static int C;
    static Point[][] map;

    public static void main(String[] args) throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer input = new StringTokenizer(bufferedReader.readLine());
        R = Integer.parseInt(input.nextToken());
        C = Integer.parseInt(input.nextToken());
        int M = Integer.parseInt(input.nextToken());

        map = new Point[R][C];
        while (M-- > 0) {
            StringTokenizer str = new StringTokenizer(bufferedReader.readLine());
            int y = Integer.parseInt(str.nextToken());
            int x = Integer.parseInt(str.nextToken());
            int speed = Integer.parseInt(str.nextToken());
            int dir = Integer.parseInt(str.nextToken());
            if (dir == 1) dir = -1;
            else if (dir == 2) dir = 1;
            else if (dir == 3) dir = 2;
            else dir = -2;

            map[y - 1][x - 1] = new Point(x - 1, y - 1, speed, dir, Integer.parseInt(str.nextToken()));
        }

        int result = 0;
        for (int i = 0; i < C; i++) {
            result += CatchShark(i);
            MoveShark();
        }
        System.out.println(result);
    }

    public static void MoveShark() {
        Queue<Point> queue = new LinkedList<>();
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] != null) {
                    queue.add(new Point(j, i, map[i][j].speed, map[i][j].dir, map[i][j].size));
                    map[i][j] = null;
                }
            }
        }

        while (!queue.isEmpty()) {
            Point cur = queue.poll();
            int move = cur.speed;

            if (cur.dir == 1 || cur.dir == -1) {//up
                while (move-- > 0) {
                    if (cur.y == 0) cur.dir = 1;
                    else if (cur.y == R - 1 ) cur.dir = -1;
                    cur.y += cur.dir;
                }
            } else if (cur.dir == 2 || cur.dir == -2) {//left
                while (move-- > 0) {
                    if (cur.x == 0) cur.dir = 2;
                    else if (cur.x == C - 1) cur.dir =  -2;
                    cur.x += cur.dir / 2;
                }
            }

            if (map[cur.y][cur.x] == null) {
                map[cur.y][cur.x] = cur;
            } else {
                if (cur.size > map[cur.y][cur.x].size) {
                    map[cur.y][cur.x] = cur;
                }
            }
        }
    }

    public static int CatchShark(int location) {
        int result = 0;

        for (int i = 0; i < R; i++) {
            if (map[i][location] != null) {
                result += map[i][location].size;
                map[i][location] = null;
                break;
            }
        }
        return result;
    }
}

class Point {
    int x, y, speed, dir, size;

    Point(int x, int y, int speed, int dir, int size) {
        this.x = x;
        this.y = y;
        this.speed = speed;
        this.dir = dir;
        this.size = size;
    }
}

일단 전체적으로 보았을 때, 가로만큼 이동하면서

상어잡기 -> 상어 이동하기를 진행한다.
```
int result = 0;
for (int i = 0; i < C; i++) {
  result += CatchShark(i); //상어잡기
  MoveShark(); //상어이동하기
}
System.out.println(result);
```
문제 다 풀고 답이 안나와서 봤는데 상어잡기부터 먼저 했다 !!!👈 문제 잘 읽자!!

상어잡기는 간단하다 !

public static int CatchShark(int location) {
  int result = 0;
  for (int i = 0; i < R; i++) {
    if (map[i][location] != null) {
      result += map[i][location].size;
      map[i][location] = null;
      break;//가까운 상어 한마리 잡으면 끝 !
    }
  }
  return result;
}

낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다.

이때, 이 조건 주의해주기!

어려웠던 상어 이동 !

public static void MoveShark() {
  //1. 일단 맵에서 상어들을 큐에 이동시켜주었다 !
  Queue<Point> queue = new LinkedList<>();
  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      if (map[i][j] != null) {
        queue.add(new Point(j, i, map[i][j].speed, map[i][j].dir, map[i][j].size));
        map[i][j] = null;
      }
    }
  }
  
  while (!queue.isEmpty()) {
    //2. 현재 상어 한마리를 빼서 이동시켜준다.
    Point cur = queue.poll();
    //2-1. move만큼 이동시켜 줄것이다.
    int move = cur.speed;
    //2-2. 방향 설명 아래 참고
    if (cur.dir == 1 || cur.dir == -1) {//-1: 위 / 1: 아래
      while (move-- > 0) {
        if (cur.y == 0) cur.dir = 1; 
        //만약 맨위에 위치하면 아래로 이동해야하기 때문에 방향을 1(아래)로 해준다.
        else if (cur.y == R - 1 ) cur.dir = -1;
        //만약 맨아래에 위치하면 위로 이동해야하기 때문에 방향을 -1(위)로 해준다.
        cur.y += cur.dir;
        //이렇게 해주면 위의 방향인경우 -1 을 더해서 위로 올라가게 되고,
        //아래의 방향인 경우 1을 더해서 아래로 내려가게 된다.
      }
    } else if (cur.dir == 2 || cur.dir == -2) {//-2: 왼쪽 / 2: 오른쪽
      //세로방향과 마찬가지다.
      while (move-- > 0) {
        if (cur.x == 0) cur.dir = 2;
        else if (cur.x == C - 1) cur.dir =  -2;
        cur.x += cur.dir / 2;
      }
    }
  
    if (map[cur.y][cur.x] == null) {
      map[cur.y][cur.x] = cur;//맵에 상어를 저장한다.
    } else {
      if (cur.size > map[cur.y][cur.x].size) {//기존 상어가 있을 경우 더 큰 상어를 넣는다.
        map[cur.y][cur.x] = cur;
      }
    }
  }
}

방향 설명 참고
조건: d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.

이였지만, 나는 계산을 쉽게 해주기 위해서
```
if (dir == 1) dir = -1;
else if (dir == 2) dir = 1;
else if (dir == 3) dir = 2;
else dir = -2;
//위: -1 , 아래: 1, 오른쪽 2: 왼쪽: -2
```

🔗 링크

정신없이 풀어서 너무 혼미하다…혼이쏙빠질정도로까다로웠다..

상어 이동이 특히 어려웠다. 처음에는 가로, 세로 길이로 나눠서 나머지 만큼 이동해야 해서 이거 계산 하는데 시간이 많이 들었다…결국은 못했지만,,저런식으로 접근하는 거 기억해야겠다.

문제: https://www.acmicpc.net/problem/17143
저장소: https://github.com/yoo-chaewon/HELLO_JAVA/blob/master/Algorithm/1.BOJ/SAMSUNG_SW/Q_17143_낚시왕.java

Twitter Facebook LinkedIn

Yoo Chaewon

[ALGORITHM]BOJ17143-낚시왕

문제

입력

출력

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력 3

예제 입력 4

예제 출력 4

나의 코드

🔗 링크

공유하기

참고

[ALGORITHM]KAKAO_2019 개발자 겨울 인턴십-크레인 인형뽑기 게임

[ALGORITHM]BOJ16235-나무 재테크

[ALGORITHM]BOJ17144-미세먼지 안녕!

[ALGORITHM]BOJ15686-치킨배달