백준 - 17143번(낚시왕)

문제 출처: https://www.acmicpc.net/problem/17143

문제

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

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

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

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

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

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

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    private static class Shark implements Comparable<Shark> {

        int r, c, s, d, z;

        public 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;
        }

        @Override
        public int compareTo(Shark o) {
            return o.z - this.z;
        }
    }

    private static List<Shark> sharkList = new ArrayList<>();
    private static int[][] directions = { { 0, 0 }, { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 }, };
    private static int R, C;

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

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        R = Integer.parseInt(tokenizer.nextToken());    // 행
        C = Integer.parseInt(tokenizer.nextToken());    // 열
        int M = Integer.parseInt(tokenizer.nextToken());    // 상어 수
        
        for (int i = 0; i < M; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int r = Integer.parseInt(tokenizer.nextToken());    // 행
            int c = Integer.parseInt(tokenizer.nextToken());    // 열
            int s = Integer.parseInt(tokenizer.nextToken());    // 속력
            int d = Integer.parseInt(tokenizer.nextToken());    // 이동 방향(1: 위, 2: 아래, 3: 오른쪽, 4: 왼쪽)
            int z = Integer.parseInt(tokenizer.nextToken());    // 크기

            sharkList.add(new Shark(r, c, s, d, z));
        }

        int ans = 0;

        if (M > 0) {
            Collections.sort(sharkList);

            for (int i = 1; i <= C; i++) {
                int r = R + 1;
                int idx = -1;

                // 잡고
                for (int j = 0; j < sharkList.size(); j++) {
                    Shark temp = sharkList.get(j);
                    if (temp.c == i && temp.r < r) {
                        r = temp.r;
                        idx = j;
                    }
                }

                if (idx != -1) {
                    ans += sharkList.get(idx).z;
                    sharkList.remove(idx);
                }

                // 이동
                moveShark();
            }
        }

        System.out.println(ans);
    }

    private static void moveShark() {
        int[][] shark = new int[R + 1][C + 1];

        // 리스트 순환하며 상어 위치 업데이트하고 배열에도 업데이트
        // 배열 업데이트 할 때 겹치는 경우 처리(상어의 크기 순으로 정렬하면 편할듯)
        for (int i = 0; i < sharkList.size(); i++) {
            Shark temp = sharkList.get(i);

            int speed = temp.s;
            if (speed > 0) {
                if (temp.d == 1 || temp.d == 2) speed %= (R - 1) * 2;
                else speed %= (C - 1) * 2;
            }

            int dy = temp.r;
            int dx = temp.c;

            for (int j = 0; j < speed; j++) {
                dy += directions[temp.d][0];
                dx += directions[temp.d][1];

                if (dy < 1 || dy > R || dx < 1 || dx > C) {
                    dy -= directions[temp.d][0];
                    dx -= directions[temp.d][1];
                    if (temp.d % 2 != 0) temp.d++;
                    else temp.d--;
                    j--;
                }
            }

            if (shark[dy][dx] != 0) {
                // 이미 다른 상어가 있는 경우(크기 순 내림차순 정렬이므로 더 큰 상어가 있다는 뜻)
                sharkList.remove(i--);
            }

            shark[dy][dx] = temp.z;
            temp.r = dy;
            temp.c = dx;
        }
    }

}

• 주어진 조건을 활용하여 모든 기능을 구현하는 문제였다.
• 처음에 상어를 잡고 그 다음 상어의 위치를 바꾸는 부분이 약간 까다로웠다.
• 각 상어의 정보를 저장하는 Shark 클래스를 만들고 이를 리스트에 넣어 관리하였다. 상어가 원래의 방향대로 진행하다 벽을 만나면 방향을 반대로 돌려 계속 진행하였는데, 이때 시간을 줄이기 위한 기술이 필요했다.
• 처음에 그냥 반복문을 돌렸다가 2400ms 대의 어마어마한 시간이 나왔다. 그래도 통과된 것이 뭔가 신기했다.🤔
• 상어들은 행 방향 이동일 때는 (R - 1) 2번, 열 방향 이동일 때는 (C - 1) 2번 이동하면 제자리로 돌아온다. 이 성질을 이용하여 이동 횟수 연산을 크게 줄일 수 있었다.