17143 - 낚시왕

문제: boj.kr/17143
날짜: 8월 24일 (토)
성공여부: X

 

 

가까운 상어를 잡는다. 그리고 상어가 움직인다.

상어가 움직인 후 같은 자리에 상어가 있으면 크기 비교 후 둘 중 하나 죽음

 

구현해야 될 로직

1. 낚시왕 move
2. 낚시왕의 상어 잡기
3. 상어 move
4. 상어끼리 잡어 먹기

⠀

여기서 가장 어려운 것이 상어의 움직임을 구현하는 것이다.

 

상어의 움직임에서 생각해볼 것이 있다. 상어는 speed를 가지며 1초에 speed만큼 움직인다. 그리고 움직이면서 벽을 만나면 방향을 바꾸고 진행한다. 이런 움직임은 0부터 speed까지 증가시키며 한 번에 한 칸씩 이동하면서 구현할 수도 있지만, 강의에서 사용한 모듈러 연산을 이용하면 시간을 좀 더 단축할 수 있다.

 

모듈러 연산을 이용하면 어떻게 구현을 하는 것일까?

강의를 보기 전, 내가 생각한 방법은 맵의 c 크기로 나누는 것이었다. 하지만, 이 방법은 안된다. 이 방법에 대해서 몇 가지 경우의 수를 계산해보면 왜 이 방법이 안되는지 알 수 있다.

 

예를 들어 아래와 같은 크기의 map이 있다고 가정하고 3칸을 이동해보자. 모듈러 연산을 적용하면 3 % 5 이므로 3이다.

p
0 1 2 3 4

  p
0 1 2 3 4 - 1칸

    p
0 1 2 3 4 - 2칸

      p
0 1 2 3 4 - 3칸

 

정확하게 움직일 수 있다. 그럼 이번엔 다른 예시를 들어보자.

 

10칸을 움직여보자. 10 % 5 = 0이다.

p
0 1 2 3 4

  p
0 1 2 3 4 - 1칸

    p
0 1 2 3 4 - 2칸

      p
0 1 2 3 4 - 3칸

        p
0 1 2 3 4 - 4칸

      p
0 1 2 3 4 - 5칸

    p
0 1 2 3 4 - 6칸

  p
0 1 2 3 4 - 7칸

p
0 1 2 3 4 - 8칸

  p
0 1 2 3 4 - 9칸

    p
0 1 2 3 4 - 10칸

 

예상하는 위치와 다르다. 여기서 좀 더 생각해보면 왜 안되는지 짐작을 할 수 있는데, 바로 c가 5라도 이동하는 칸 수는 4칸이기 때문이다. 그래서 5로 모듈러 연산을 하면 5칸을 이동한 것이 되어버려 예상하는 값과 다른 것이다. 그럼 4칸을 기준으로 모듈러 연산을 하면 된다. 10 % 4 = 2이다. 예상한 것과 같은 위치가 나왔다.

 

그럼 또 다른 예시로 왕복을 하지 않고 중간에 멈추는 경우 중 7칸을 예시로 알아보자. 7 % 4 = 3이다.

p
0 1 2 3 4

  p
0 1 2 3 4 - 1칸

    p
0 1 2 3 4 - 2칸

      p
0 1 2 3 4 - 3칸

        p
0 1 2 3 4 - 4칸

      p
0 1 2 3 4 - 5칸

    p
0 1 2 3 4 - 6칸

  p
0 1 2 3 4 - 7칸

 

예상하는 위치와 다르다. 하지만 4에서 3을 빼면 예상하는 위치가 나온다는 것을 알 수 있다. 하지만, 어떤 기준으로 4에서 3을 빼는 기준을 정할 것인가?에 대해서 답을 내리지 못했다....

 

그래서 강의를 봤는데 어느정도 비슷한 방식이었다. 하지만, 강의는 map의 c 크기 즉, 편도가 아니라 왕복을 기준으로 모듈러 연산을 했다. 이 방식을 이용하면 '배열의 범위를 넘어서면' 이라는 기준을 세울 수 있다.

 

예를 들어 위의 3칸, 10칸을 이동하는 경우는 왕복에 8칸이 걸리므로 8로 모듈러 연산을 하면 각각 3칸, 2칸이 나온다. 10칸이나 3칸이나 원래의 방향대로 이동하는 것이므로 그냥 이동하면 된다. 하지만, 마지막 위치에서 방향이 전환된 경우에는 배열의 범위를 넘어서는 수가 나온다. 바로 위의 7칸도 그렇고 13칸도 그렇다. 이런 경우에만 반대편에서 다시 나머지를 이동하는 로직을 구현하면 된다.

 

이것만 알면 !!!

나머진 쉽게 구현할 수 있다.

 

코드

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, 1, -1};

    static int r, c, m;
    static int[][] map;
    static int[][] temp;
    static int ret = 0;

    static class shark {
        int y, x;
        int size;
        int dir;
        int speed;
        boolean death;

        public shark(int y, int x, int s, int d, int z) {
            this.y = y;
            this.x = x;
            this.speed = s;
            this.dir = d;
            this.size = z;
            this.death = false;
        }

        public shark() {}
    }

    static ArrayList<shark> sharks = new ArrayList<>();

    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());

        map = new int[r][c];
        sharks.add(new shark());
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken())-1;
            int x = Integer.parseInt(st.nextToken())-1;
            int s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken())-1;
            int size = Integer.parseInt(st.nextToken());
            sharks.add(new shark(y, x, s, d, size));

            if (d <= 1) sharks.get(i).speed %= (r - 1);
            else sharks.get(i).speed %= (c - 1);
            map[y][x] = i;
        }

        for (int t = 0; t < c; t++) {

            for (int y = 0; y < r; y++) {
                if (map[y][t] > 0) {
                    sharks.get(map[y][t]).death = true;
                    ret += sharks.get(map[y][t]).size;
                    map[y][t] = 0;
                    break;
                }
            }

            temp = new int[r][c];
            for (int idx = 1; idx <= m; idx++) {
                if (sharks.get(idx).death) continue;

                int y = sharks.get(idx).y;
                int x = sharks.get(idx).x;
                int s = sharks.get(idx).speed;
                int d = sharks.get(idx).dir;
                int ny, nx;

                boolean flag = false;
                while (true) {
                    ny = y + s * dy[d];
                    nx = x + s * dx[d];

                    if (ny < r && nx < c && ny >= 0 && nx >= 0) break;
                    if (d <= 1) {
                        if (ny < 0) {
                            s -= y;
                            y = 0;
                        } else {
                            s -= r - 1 - y;
                            y = r-1;
                        }
                    } else {
                        if (nx < 0) {
                            s -= x;
                            x = 0;
                        } else {
                            s -= c-1-x;
                            x = c-1;
                        }
                    }

                    d ^= 1;
                }

                if (temp[ny][nx] > 0) {
                    if (sharks.get(temp[ny][nx]).size > sharks.get(idx).size)
                        sharks.get(idx).death = true;
                    else {
                        sharks.get(temp[ny][nx]).death = true;
                        temp[ny][nx] = idx;
                    }
                } else temp[ny][nx] = idx;

                sharks.get(idx).y = ny;
                sharks.get(idx).x = nx;
                sharks.get(idx).dir = d;
            }

            for (int i = 0; i < r; i++) map[i] = temp[i].clone();
        }

        System.out.println(ret);
    }
}