백준 17143번. 낚시왕 (Java)

Problem

• 문제 링크

낚시왕이 왼쪽에서 오른쪽 끝으로 이동하는 동안 잡은 상어 크기의 합을 구하는 문제입니다.

상어는 속력과 방향, 크기를 갖고 있으며 매 초마다 바라보는 방향으로 속력만큼 칸을 이동합니다.

만약 상어가 범위 밖으로 벗어나려고 하면 방향을 바꿔서 이동합니다.

Solution

문제에서 주어진 대로 구현하면 됩니다.

Shark 클래스를 선언해서 상어의 크기, 속력, 방향을 정의했고 좌표에 맞춰서 2차원 배열인 sharks 에 저장했습니다.

이 문제는 상어를 움직이는게 핵심입니다.

처음에는 계산하기 귀찮아서 단순하게 반복했더니.. Java 8 에서는 통과하는데 Java 11 이나 OpenJDK 환경에서는 시간초과가 발생했습니다.

따라서 어느정도 이동거리에 대한 최적화가 필요합니다.

몇 개의 예시를 만들어서 테스트 해보면 알 수 있지만 상어가 어디 위치에 있던, 일정한 거리를 이동하면 다시 원래 위치와 방향으로 돌아옵니다.

공식은 상어가 위아래로 움직일 땐 (R - 1) * 2 이고 좌우로 움직일 땐 (C - 1) * 2 입니다.

예를 들어 상어의 속력이 9 이고 위아래로 움직이며 R == 4 인 맵에 있다고 가정합니다.

상어는 어느 좌표에 있어도 6 만큼 이동하면 다시 원래 자리와 방향(중요)으로 돌아옵니다.

그렇기 때문에 9 % 6 인 3 만큼만 이동하면 상어의 최종 도착지가 됩니다.

최종 연산까지 구하기엔 아무래도 상어의 방향까지 구하기가 귀찮아서.. 나머지 연산 이후에는 직접 반복문으로 이동했습니다.

주의할 점

1. 상어는 맨 끝에 있으면서 바깥 방향을 바라본 채로 시작할 수 있습니다.
2. 상어 경쟁을 실시간으로 처리하면 이동하기 전 상어와 경쟁할 수 있기 때문에 경쟁은 모든 이동이 끝난 후에 해야 합니다.

Java Code

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

class Main {

    static class Shark {
        int speed, direction, size;
    }

    static int R, C, M;
    static int answerSumOfSize = 0;
    static Shark[][] sharks;

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

        // 격자판의 크기 R, C, 상어의 수 M
        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        sharks = new Shark[R][C];

        // M 개의 줄에 상어의 정보
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            Shark shark = new Shark();
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            shark.speed = Integer.parseInt(st.nextToken());
            shark.direction = Integer.parseInt(st.nextToken());
            shark.size = Integer.parseInt(st.nextToken());
            sharks[r - 1][c - 1] = shark;
        }

        solution();
        System.out.println(answerSumOfSize);
    }

    // 낚시왕이 오른쪽으로 한칸 이동하는건 반복문의 index 로 표현
    // 현재 상어의 위치 중 제일 가까운 상어를 잡고 상어 이동 반복
    private static void solution() {
        for (int i = 0; i < C; i++) {
            fishing(i);
            moveAllSharks();
        }
    }

    // 현재 위치에서 가장 가까이에 있는 상어를 잡는다.
    private static void fishing(int col) {
        for (int i = 0; i < R; i++) {
            if (sharks[i][col] != null) {
                answerSumOfSize += sharks[i][col].size;
                sharks[i][col] = null;
                return;
            }
        }
    }

    private static void moveAllSharks() {
        Shark[][] nextSharks = new Shark[R][C];

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                moveShark(nextSharks, i, j);
            }
        }

        // 이동 완료한 배열로 덮어 씌우기
        for (int i = 0; i < R; i++) {
            sharks[i] = Arrays.copyOf(nextSharks[i], C);
        }
    }

    private static void moveShark(Shark[][] nextSharks, int i, int j) {
        Shark shark = sharks[i][j];

        if (shark == null) {
            return;
        }

        // direction 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽
        // 위아래는 R, 좌우는 C 가 X 라고 할 때 (X - 1) * 2 만큼 이동하면 동일한 위치, 방향으로 돌아온다.
        // 그러므로 상어의 속도에서 (X - 1) * 2 을 나눈 나머지만큼만 이동하면 된다.
        // 총 이동해야 할 거리 = shark.speed % ((X - 1) * 2)
        int X = shark.direction < 3 ? R : C;
        int moveDistance = shark.speed % ((X - 1) * 2);
        int row = i;
        int col = j;

        // 움직이는 거리를 구한 후에는 직접 이동시킴
        // (최종 위치를 구했을 때 방향까지 계산하기 귀찮아서.. 직접 이동)
        for (int k = 0; k < moveDistance; k++) {
            if (shark.direction == 1) {
                row--;
                if (row < 0) {
                    shark.direction = 2;
                    row = 1;
                }
            } else if (shark.direction == 2) {
                row++;
                if (row > R - 1) {
                    shark.direction = 1;
                    row = R - 2;
                }
            } else if (shark.direction == 3) {
                col++;
                if (col > C - 1) {
                    shark.direction = 4;
                    col = C - 2;
                }
            } else {
                col--;
                if (col < 0) {
                    shark.direction = 3;
                    col = 1;
                }
            }
        }

        // 만약 이미 상어가 있으면 크기를 비교해서 사이즈 큰 놈을 남긴다
        if (nextSharks[row][col] != null && nextSharks[row][col].size > shark.size) {
            return;
        }

        nextSharks[row][col] = shark;
    }
}