[백준] 17143번 - 낚시왕 (java)

Baekjoon 17143 - 낚시왕 (클릭 시 이동)

문제

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

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

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

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

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

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

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	27445	7547	4185	24.189%

입력

첫째 줄에 격자판의 크기 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) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.

두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

출력

낚시왕이 잡은 상어 크기의 합을 출력한다.

풀이

시키는대로 하면 되는 구현 and 시뮬레이션 문제이다.

1. 낚시왕이 오른쪽으로 한 칸 이동한다.
2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
3. 상어가 이동한다. 이동을 완료한 후에 같은 위치에 상어가 존재하면 크기가 큰 상어가 나머지 상어를 잡아먹는다.

위 과정이 올바르게 동작할 수 있도록 각 동작을 구현한다.

과정

시작에 앞서 상어의 정보를 저장할 클래스를 구현했다.

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

    public Shark(int z) {
        super();
        this.z = z;
    }

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

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Shark other = (Shark) obj;
        if (z != other.z)
            return false;
        return true;
    }
}

equals 메소드를 오버라이드 한 이유는 상어의 크기(z)는 중복되는 값이 존재하지 않는다.

상어의 크기로 상어를 구분할 수 있다는 의미이기도 하다.

따라서, 상어의 정보가 저장되어있는 list에서 찾고자 하는 상어가 있으면 z를 이용하여 찾아낼 수 있도록 했다.

1. 낚시왕이 오른쪽으로 한 칸 이동한다.

for문을 통해 2번에 있는 메소드를 수행할 것이다.

2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.

static void fishing(int c) {
    for (int i = 1; i <= R; i++) {
        if (map[i][c] > 0) {
            answer += map[i][c];
            list.remove(new Shark(map[i][c]));
            map[i][c] = 0;
            return;
        }
    }
}

낚시왕은 해당 열에서 가장 작은 row에 있는 상어를 잡아낸다.

파라미터로 colomn No 를 넣어주고 그 위치에서 각 행을 탐색해보고 상어가 있으면 잡아내게 된다.

map에는 해당 위치에 존재하고 있는 상어의 크기가 저장되어 있다.

list.remove(new Shark(map[i][c]))로 해당 상어와 크기가 같은 객체를 만들어서 List에서 크기가 같은 상어를 찾아내 삭제한다.

3. 상어가 이동한다.

static void swimming() {
    for (int i = 0; i < list.size(); i++) {
        Shark temp = list.get(i);
        for (int j = 0; j < temp.s; j++) {
            int nr = temp.r + deltas[temp.d][0];
            int nc = temp.c + deltas[temp.d][1];
            if (isIn(nr, nc)) {
                temp.r = nr;
                temp.c = nc;
            } else {
                if (temp.d % 2 == 0)
                    temp.d++;
                else
                    temp.d--;
                j--;
            }
        }
    }
}

각 상어에 대해서 이동을 진행한다.

모든 상어는 방향과 속도를 가지고 있다. 맵을 벗어나게 되면 반대방향으로 즉시 돌아 이동하게 된다.

4번라인의 for문은 속도만큼 탐색을 진행하는데 7번라인을 보면 이동할 수 있는 위치라면( map의 크기를 벗어나지 않는 r,c이면 ) 현재 위치로 만들어준다.

그렇지 않다면 방향을 바꿔준다.

방향 d가 의미하는것은 0: 상, 1: 하, 2 : 우, 3: 좌 이다.

반대방향으로 회전한다는것은 0-> 1 / 2 -> 3 또는 1 -> 0 / 3 ->2를 뜻하게 된다.

0 또는 2일 때 즉, 2로 나눈 나머지(mod)가 0일때는 +1을 하고

1또는 3일 때, 2로나눈 나머지가 1일때는 -1을 한다.

그리고 맵의 밖을 탐색한것은 횟수로 치지 않아야하므로 j를 1만큼 감소해준다.

4. 이동을 완료한 후에 같은 위치에 상어가 존재하면 크기가 큰 상어가 나머지 상어를 잡아먹는다.

static int[][] setUp() {
    int[][] tempMap = new int[R + 1][C + 1];
    for (int i = 0; i < list.size(); i++) {
        Shark temp = list.get(i);
        if (tempMap[temp.r][temp.c] == 0) {
            tempMap[temp.r][temp.c] = temp.z;
        } else {
            if (tempMap[temp.r][temp.c] < temp.z) {
                list.remove(new Shark(tempMap[temp.r][temp.c]));
                tempMap[temp.r][temp.c] = temp.z;

            } else {
                list.remove(new Shark(temp.z));
            }
            i--;
        }
    }
    return tempMap;
}

리스트에서 상어들을 탐색하며 상어의 r,c에 맞게 상어의 크기를 넣어준다.

5번 라인처럼 해당 위치에 상어가 존재하지 않는다면 상어의 크기를 넣어주지만

그렇지 않다면 상어의 크기를 비교하고 더 작은 상어를 삭제해준다.

상어를 삭제하면 list의 크기가 1만큼 감소하게 된다.

만약 현재 수행하고 있는 i가 5라면 현재 상어를 삭제했을때 5번 인덱스에 있는 상어는 다른 상어를 가리키게 된다.

다음 for문을 진행할때 정상적인 탐색을 진행하려면 i를 1만큼 감소시켜야 하므로 상어를 삭제했다면 i를 1만큼 감소시켜준다.

최종 소스코드

package BJ_Practice.Gold;

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

public class BJ_G2_17143_낚시왕 {
    static int R, C, M;
    static int answer = 0;
    static int[][] map;
    static int[][] deltas = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
    static StringTokenizer st;
    static List<Shark> list = new ArrayList<>();

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

        public Shark(int z) {
            super();
            this.z = z;
        }

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

        // 크기는 Unique하므로 크기가 같으면 같은 객체로 판단.
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Shark other = (Shark) obj;
            if (z != other.z)
                return false;
            return true;
        }
    }

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

        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[R + 1][C + 1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken()) - 1;
            int z = Integer.parseInt(st.nextToken());
            map[r][c] = z;
            list.add(new Shark(r, c, s, d, z));
        }

        for (int i = 1; i <= C; i++) {
            fishing(i);
            swimming();
            map = setUp();
        }
            System.out.println(answer);

    }
    //낚시
    static void fishing(int c) {
        for (int i = 1; i <= R; i++) {
            if (map[i][c] > 0) {
                answer += map[i][c];
                list.remove(new Shark(map[i][c]));
                map[i][c] = 0;
                return;
            }
        }
    }

    //헤엄
    static void swimming() {
        for (int i = 0; i < list.size(); i++) {
            Shark temp = list.get(i);
            for (int j = 0; j < temp.s; j++) {
                int nr = temp.r + deltas[temp.d][0];
                int nc = temp.c + deltas[temp.d][1];
                if (isIn(nr, nc)) {
                    temp.r = nr;
                    temp.c = nc;
                } else {
                    if (temp.d % 2 == 0)
                        temp.d++;
                    else
                        temp.d--;
                    j--;
                }
            }
        }
    }

    //맵에 집어넣으면서 이미 어떤 값이 들어가 있으면 크기비교를 하고 작은건 리스트에서 삭제.
    static int[][] setUp() {
        int[][] tempMap = new int[R + 1][C + 1];
        for (int i = 0; i < list.size(); i++) {
            Shark temp = list.get(i);
            if (tempMap[temp.r][temp.c] == 0) {
                tempMap[temp.r][temp.c] = temp.z;
            } else {
                if (tempMap[temp.r][temp.c] < temp.z) {
                    list.remove(new Shark(tempMap[temp.r][temp.c]));
                    tempMap[temp.r][temp.c] = temp.z;

                } else {
                    list.remove(new Shark(temp.z));
                }
                i--;
            }
        }
        return tempMap;
    }

    static boolean isIn(int r, int c) {
        return r > 0 && r < R + 1 && c > 0 && c < C + 1;
    }
}

리뷰

상어를 리스트에 넣고 탐색하게 되는데 삭제가 빈번하다고 해도 조회하는 횟수가 훨씬 많다.

따라서 LinkedList보다는 ArrayList를 사용했고 삭제를 진행할 때 마다 삭제한 위치 이후의 인덱스를 모두 1칸씩 당겨오는 작업이 ArrayList의 remove메소드에 포함되어 있으므로 시간이 조금 오래 걸리는 편이다.