[BOJ/Simulation] 백준 17143 - 낚시왕 (Java)

17143 - 낚시왕

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

문제

RxC인 격자판에서 낚시왕이 상어 낚시/ 격자판의 각 칸은 (r, c)로 나타낼 수 있는데 r은 행, c는 열이고 (R, C)는 가장 오른쪽 아래
칸에는 상어가 최대 1마리 들어있을 수 있고 상어는 크기와 속도를 가지고 있음
낚시왕은 처음에 1번 열의 한 칸 위에 있음

1초 동안 순서대로 일어나며, 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동 멈춤
1. 낚시왕 오른쪽으로 한 칸 이동
2. 낚시왕이 있는 열에 있는 상어 중 땅과 제일 가까운 상어 잡음/ 상어 잡으면 격자판에서 사라짐
3. 상어 이동
상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초
상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우 방향을 반대로 바꿔 속력 유지한채로 이동
상어가 이동 마친 후에 한 칸에 상어가 2마리 이상 있을 수 있고, 크기가 가장 큰 상어가 나머지 상어 모두 잡아먹음

입력
첫째 줄: 격자판의 크기 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)
(d가 1: 위/ 2: 아래/ 3: 오른쪽/ 4: 왼쪽)
출력: 낚시왕이 잡은 상어 크기의 합

---

풀이

Shark 클래스

• r, c: 위치 (0-index)
• s: 속력 (이동 칸 수)
• d: 방향 (1: 위/ 2: 아래/ 3: 오른쪽/ 4: 왼쪽)
  • `int[] dr = {0, -1, 1, 0, 0}`
  • `int[] dc = {0, 0, 0, 1, -1}`
  • ex. 위: dr[1] = -1, dc[1] = 1 -> (r - 1, c)
• z: 크기 (잡거나 충돌 시 비교 기준)

static class Shark {
    int r, c, s, d, z;

    Shark(int r, int c, int s, int d, int z) {
        this.r = r;
        this.c = c;
        this.s = s;
        this.d = d;
        this.z = z;
    }
}

 

`catchShark(col)`: 해당 열에서 상어 잡기

• `col` 열에 있는 상어 중 r이 가장 작은(가장 위) 상어 찾음
• O -> 상어를 리스트에서 제거, 크기 z `return`

static int catchShark(int col) {
    Shark target = null;
    int minRow = R;

    for (Shark s : sharks) {
        if (s.c == col && s.r < minRow) {
            minRow = s.r;
            target = s;
        }
    }

    if (target != null) {
        sharks.remove(target);
        return target.z;
    }

    return 0;
}

 

`moveSharks()`: 모든 상어 이동 + 충돌 처리

• 상어 벽에 부딪히면 방향 반대로 바꾸며 왕복
  • 세로: `s.d == 1 || s.d == 2` -> `(R - 1) * 2`
  • 가로: `(C - 1) * 2`
• 1칸씩 이동하면서 벽이면 방향 반전
• 같은 칸에 여러 마리 -> 큰 상어만 남김
  • `Map<Intger, Shark> HM = new HashMap<>()`: 칸 하나당 상어 하나
  • `key = s.r * C + s.c`: 2차원 좌표 (r, c) -> 1차원 정수로 바꿈
    • 2차원 배열의 1차원 인덱싱: `index = row * width + col`
  • `!HM.containsKey(key) || HM.get(key).z < s.z`: 칸에 아직 상어 X or 이미 있는 상어보다 지금 상어가 큼
    -> `HM.put(key, s)`: 지금 상어로 교체

static List<Shark> moveSharks() {
    Map<Integer, Shark> HM = new HashMap<>();

    for (Shark s : sharks) {
        int move = s.s;

        if (s.d == 1 || s.d == 2) move %= (R - 1) * 2;
        else move %= (C - 1) * 2;

        for (int i = 0; i < move; i++) {
            int nr = s.r + dr[s.d];
            int nc = s.c + dc[s.d];

            if (nr < 0 || nc < 0 || nr >= R || nc >= C) {
                if (s.d == 1) s.d = 2;
                else if (s.d == 2) s.d = 1;
                else if (s.d == 3) s.d = 4;
                else if (s.d == 4) s.d = 3;

                nr = s.r + dr[s.d];
                nc = s.c + dc[s.d];
            }

            s.r = nr;
            s.c = nc;
        }

        int key = s.r * C + s.c;
        if (!HM.containsKey(key) || HM.get(key).z < s.z) {
            HM.put(key, s);
        }
    }

    return new ArrayList<>(HM.values());
}

---

코드

import java.io.*;
import java.util.*;

// 낚시왕
public class boj_17143 {
    static class Shark {
        int r, c, s, d, z;

        Shark(int r, int c, int s, int d, int z) {
            this.r = r;
            this.c = c;
            this.s = s;
            this.d = d;
            this.z = z;
        }
    }

    static int R, C, M;
    static int[] dr = {0, -1, 1, 0, 0};
    static int[] dc = {0, 0, 0, 1, -1};
    static List<Shark> sharks;

    static int catchShark(int col) {
        Shark target = null;
        int minRow = R;

        for (Shark s : sharks) {
            if (s.c == col && s.r < minRow) {
                minRow = s.r;
                target = s;
            }
        }

        if (target != null) {
            sharks.remove(target);
            return target.z;
        }

        return 0;
    }

    static List<Shark> moveSharks() {
        Map<Integer, Shark> HM = new HashMap<>();

        for (Shark s : sharks) {
            int move = s.s;

            if (s.d == 1 || s.d == 2) move %= (R - 1) * 2;
            else move %= (C - 1) * 2;

            for (int i = 0; i < move; i++) {
                int nr = s.r + dr[s.d];
                int nc = s.c + dc[s.d];

                if (nr < 0 || nc < 0 || nr >= R || nc >= C) {
                    if (s.d == 1) s.d = 2;
                    else if (s.d == 2) s.d = 1;
                    else if (s.d == 3) s.d = 4;
                    else if (s.d == 4) s.d = 3;

                    nr = s.r + dr[s.d];
                    nc = s.c + dc[s.d];
                }

                s.r = nr;
                s.c = nc;
            }

            int key = s.r * C + s.c;
            if (!HM.containsKey(key) || HM.get(key).z < s.z) {
                HM.put(key, s);
            }
        }

        return new ArrayList<>(HM.values());
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        sharks = new ArrayList<>();
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            int s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());
            sharks.add(new Shark(r, c, s, d, z));
        }

        int ans = 0;
        for (int col = 0; col < C; col++) {
            ans += catchShark(col);
            sharks = moveSharks();
        }

        System.out.println(ans);
    }
}