[BOJ] 17143 낚시왕 - JAVA

ONE·2022년 4월 21일
0

Baekjoon Online Judge

목록 보기
16/16

📚 Problem

17143 낚시왕

📝 Solution

Key Idea

  • 다른 시뮬레이션 문제들과 유사하게 조건에 부합하게 구현만 하면 된다
  • 주의해야할 점은 상어를 삭제할 때 이동을 모두 끝낸 후에 해당되는 상어를 제거해야되는 것이다
  • 처음에는 상어들의 목록을 ArrayList 를 이용해 구현했었는데 그러면 상어를 삭제할때마다 index 가 변경되어 상어 Class 에 num field를 따로 두어 제거할 상어를 찾을 때 계속해서 num 을 이용해 index를 찾아야하는 불편함이 있었다
  • 위를 해결하기 위해 Map 을 이용해 상어의 num 을 key 값, 상어 class 를 value 로 두어 코드를 간략화했고 소요 시간도 감소할 줄 알았으나...
  • 메모리 사용량은 거의 2배로 뛰고 시간도 조금 더 걸렸다...
  • 두 자료형에서 get 을 할때의 소요시간이 더 걸리는 것인지 파라미터로 넘길 때에 메모리의 사용량에서 차이가 있는지 한번 알아봐야 할 것 같다
        int sizeSum = 0;
        int[][] location = new int[R + 1][C + 1];
        Map<Integer, Shark> map = new HashMap<>();

        for(int[] row : location)
            Arrays.fill(row, -1);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            Shark shark = new Shark(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            map.put(i, shark);
            location[shark.r][shark.c] = i;
        }

        for (int i = 1; i <= C; i++) {
            int num = findNearest(location, R, i);

            if (num != -1) {
                Shark shark = map.get(num);
                sizeSum += shark.z;
                location[shark.r][shark.c] = -1;
                map.remove(num);
            }
            move(R, C, map, location);
        }

💻 Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Shark {
    int r;
    int c;
    int s;
    int d;
    int 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;
    }

    public void changeDir() {
        switch (this.d) {
            case 1:
                this.d = 2;
                break;
            case 2:
                this.d = 1;
                break;
            case 3:
                this.d = 4;
                break;
            case 4:
                this.d = 3;
        }
    }
}

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int sizeSum = 0;
        int[][] location = new int[R + 1][C + 1];
        Map<Integer, Shark> map = new HashMap<>();

        for(int[] row : location)
            Arrays.fill(row, -1);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            Shark shark = new Shark(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            map.put(i, shark);
            location[shark.r][shark.c] = i;
        }

        for (int i = 1; i <= C; i++) {
            int num = findNearest(location, R, i);

            if (num != -1) {
                Shark shark = map.get(num);
                sizeSum += shark.z;
                location[shark.r][shark.c] = -1;
                map.remove(num);
            }
            move(R, C, map, location);
        }

        System.out.println(sizeSum);
    }

    private static int findNearest(int[][] location, int R, int C) {
        int sharkNum = -1;

        for (int i = 1; i <= R; i++)
            if(location[i][C] != -1) {
                sharkNum = location[i][C];
                break;
            }
        return sharkNum;
    }

    private static boolean isOutOfBound(int x, int y, int R, int C) {
        return x == 0 || y == 0 || x > R || y > C;
    }

    private static void move(int R, int C, Map<Integer, Shark> map, int[][] location) {
        int[] dx = {0, -1, 1, 0, 0};
        int[] dy = {0, 0, 0, 1, -1};

        for (Shark shark : map.values()) {
            int direction = shark.d, distance = shark.s;
            int x = shark.r, y = shark.c;
            location[x][y] = -1;

            while (distance > 0) {
                if (isOutOfBound(x + dx[direction], y + dy[direction], R, C)) {
                    shark.changeDir();
                    direction = shark.d;
                }

                x += dx[direction];
                y += dy[direction];

                distance--;
            }
            shark.r = x;
            shark.c = y;
        }

        ArrayList<Integer> removeList = new ArrayList<>();

        for (int num : map.keySet()) {
            Shark shark = map.get(num);
            if (location[shark.r][shark.c] != -1) {
                Shark original = map.get(location[shark.r][shark.c]);

                if (original.z > shark.z)
                    removeList.add(num);
                else {
                    removeList.add(location[shark.r][shark.c]);
                    location[shark.r][shark.c] = num;
                }
            }
            else
                location[shark.r][shark.c] = num;
        }

        for(int num : removeList)
            map.remove(num);
    }
}
profile
New, Strange, Want to try

0개의 댓글