[BOJ/Java] 17143: 낚시왕

문제

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

낚시왕이 낚시를 하는 `R`x`C` 격자판이 있다.

초기 상태에는 칸마다 상어가 최대 한 마리 있을 수 있다. 상어는 크기와 속도를 가진다.

낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있고, 마지막 열의 오른쪽으로 이동하면 이동이 끝난다.

1초 동안에는 다음의 일이 일어난다.

1. 낚시왕이 오른쪽으로 한 칸 이동한다.
2. 낚시왕이 위치한 열에서 땅(자신)과 제일 가까운 상어를 한 마리 잡는다.
3. 상어가 이동한다.

상어는 주어진 속도로 이동하며, 속도 1은 1초에 한 칸을 이동할 수 있다는 것을 의미한다. 만약 격자의 경계를 넘어가면 방향을 반대로 바꿔 같은 속력으로 이동한다.

상어가 이동하면 한 칸에 두 마리 이상의 상어가 있을 수 있는데, 제일 크기가 큰 상어를 제외한 나머지 상어는 잡아 먹힌다.

낚시왕이 이동을 멈출 때까지 잡은 상어의 크기의 총합을 구하면 된다.

`M`마리의 상어 정보가 주어진다.

• 2 ≤ `R`, `C` ≤ 100, 0 ≤ `M` ≤ R×C
• 상어의 속도, 방향, 크기 `s`, `d`, `z` (1 ≤ `r` ≤ `R`, 1 ≤ `c` ≤ `C`, 0 ≤ `s` ≤ 1,000, 1 ≤ `d` ≤ 4, 1 ≤ `z` ≤ 10,000)

 

풀이

문제에 주어진 로직대로 크게 상어를 잡는 `catchShark`와 모든 상어를 이동하는 `moveSharks`로 함수를 나누어 구현했다.

 

`catchShark`는 현재 열에서 땅에서 다음 행으로 한 칸씩 이동하며 상어가 있으면 잡고 함수를 종료한다.

 

`moveSharks`는 모든 상어의 다음 위치와 방향을 계산하는 `getNext` 함수로 상어의 다음 위치와 방향을 계산한다. 만약 다음 칸이 비어 있지 않거나, 해당 칸에 있던 상어의 크기가 더 크다면, 잡아먹히므로 해당 상어는 사라지게 된다. 상어가 없는 빈 격자에 이전 상어의 위치를 가져와 한 초의 격자 상태를 저장한다. 모든 상어의 계산이 끝나면 이를 원본 배열에 반영한다.

 

`getNext` 함수가 이번 문제의 핵심 로직이다. 상어는 한 번에 최대 1,000칸을 이동할 수 있으므로 만약 속도만큼 반복하게 되면 시간 초과가 발생한다. 때문에 상어의 속도를 고려해 이동의 반복을 최소화하여 다음 위치를 계산해야 한다.

 

문제를 최적화하기 위한 아이디어는 다음과 같다.

 

격자의 크기가 100이라고 가정해보자. 이때 상어의 속도가 1,000이라고 가정하면, 5번을 왕복할 수 있다. 출발점에서 격자의 크기인 100 * 2(200) 만큼 움직이면 출발점으로 되돌아 온다. 속도가 1,000이든 200이든 다음의 위치는 동일하다.

 

문제에서는 결국 다음의 위치만 생각하면 되므로 speed = speed % cycle이 성립한다. `speed %= cycle`로 속도를 축소함으로써 불필요한 반복을 줄이며 다음 위치를 계산한다.

// speed %= cycle
if (d == UP || d == DOWN) s %= (2 * (r - 1));
else s %= (2 * (c - 1));

for (int i = 0; i < s; i++) {
    // 줄인 속도만큼만 반복해서 이동
}

 

또, 반복을 사용하지 않으면서 다음 위치를 계산하여 좀 더 최적화할 수 있는 방법이 있다.

 

우선 왕복 이동을 선형 좌표해 왕복 경로를 격자가 아닌 일직선 경로라고 가정해보자.

예를 들어 행의 크기 `R`이 4라면, 상어는 행 0 → 1 → 2 → 3 → 2 → 1 → 0 이런 식으로 왕복하게 된다.
이 왕복 경로를 단순한 선형 경로로 보면, 왕복 경로의 길이는 2 * (R - 1)이 된다.

즉, 아래와 같이 좌표를 정리할 수 있다:

왕복 좌표	0	1	2	3	4	5
행(i)	0	1	2	3	2	1

 

이제 상어의 현재 위치를 선형 경로 상의 좌표로 환산해준다.

그 다음, 속도만큼 더한 뒤 다시 실제 격자 위치로 복원하면 된다. 이 과정에서 반복없이 다음 위치를 계산할 수 있다.

이를 위한 기본 로직은 다음과 같다.

int cycle = 2 * (R - 1);
int pos = (dir == DOWN) ? i : (cycle - i); // 방향에 따라 반대쪽에서 시작
int newPos = (pos + speed) % cycle; // 변환된 좌표에서 왕복 이동한 위치

// 새 위치가 격자의 범위를 넘으면 위치를 보정하고 방향을 바꾼다.
if (newPos < R) {
    i = newPos;
    dir = DOWN;
} else {
    i = cycle - newPos;
    dir = UP;
}

속도를 축소해 반복한 코드와 비교해 약 200ms의 성능 향상을 보여준다.

 

코드

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

public class Main {
    static int r, c, m;
    static Shark[][] map;
    static class Shark {
        int s, d, z;
        public Shark(int s, int d, int z) {
            this.s = s; this.d = d; this.z = z;
        }
    }
    static int[] dx = {0, -1, 1, 0, 0};
    static int[] dy = {0, 0, 0, 1, -1};
    static final int UP = 1, DOWN = 2, RIGHT = 3, LEFT = 4;
    static int totalZ = 0;

    public static void main(String[] args) throws IOException {
        // 칸에 상어는 최대 한 마리, 속도와 크기를 가진다.
        // 낚시왕이 C + 1에 도달하면 종료
        // 1초 동안,
        // 1. 낚시왕이 오른쪽으로 한 칸 이동한다.
        // 2. 해당 열에서 땅과 제일 가까운 상어를 잡는다.
        // 3. 상어가 이동한다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new Shark[r][c];
        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()); // 크기
            map[r][c] = new Shark(s, d, z);
        }

        // c초 동안
        for (int i = 0; i < c; i++) {
            // 상어를 잡는다.
            catchShark(i);
            // 상어가 움직인다.
            moveSharks();
        }

        System.out.println(totalZ);
    }

    static void catchShark(int col) {
        for (int i = 0; i < r; i++) {
            if (map[i][col] != null) {
                totalZ += map[i][col].z;
                map[i][col] = null;
                return;
            }
        }
    }

    static void moveSharks() {
        Shark[][] currentMap = new Shark[r][c];

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++){
                if (map[i][j] != null) {
                    Shark current = map[i][j];
                    int[] next = getNext(i, j, current.s, current.d);
                    int nr = next[0], nc = next[1], nd = next[2];
                    // 빈 칸 혹은 더 큰 경우 이동해서 잡아먹음
                    if (currentMap[nr][nc] == null || currentMap[nr][nc].z < current.z) {
                        currentMap[nr][nc] = new Shark(current.s, nd, current.z);
                    }
                }
            }
        }

        map = currentMap;
    }

    static int[] getNext(int cr, int cc, int s, int d) {
        if (d == UP || d == DOWN) {
            s %= (2 * (r - 1));
        } else {
            s %= (2 * (c - 1));
        }

        for (int i = 0; i < s; i++) {
            int nr = cr + dx[d];
            int nc = cc + dy[d];
            // 경계를 만나면 방향 전환
            if (nr < 0 || nr >= r || nc < 0 || nc >= c) {
                switch (d) {
                    case UP: d = DOWN; break;
                    case DOWN: d = UP; break;
                    case LEFT: d = RIGHT; break;
                    case RIGHT: d = LEFT; break;
                }

                nr = cr + dx[d];
                nc = cc + dy[d];
            }
            
            cr = nr;
            cc = nc;
        }
        
        return new int[]{cr, cc, d};
    }
}