P.17143 낚시왕

코드

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

public class Main {

    static int r, c, m;
    static int[][] map;
    static Map<Integer, Shark> sharks = new HashMap<>();

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

    static int res = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        r = line[0]; c = line[1]; m = line[2];
        map = new int[r][c];
        for (int i = 0; i < m; i++) {
            line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            sharks.put(i + 1, new Shark(line[0] - 1, line[1] - 1, line[2], line[3], line[4]));
            map[line[0] - 1][line[1] - 1] = i + 1;
        }

        for (int i = 0; i < c; i++) {
            catchShark(i);
            moveShark();
        }

        bw.write(Integer.toString(res));
        bw.flush();
    }

    private static void moveShark() {
        List<Integer> removeList = new ArrayList<>();
        int[][] copyMap = new int[r][c];

        for (Map.Entry<Integer, Shark> entry : sharks.entrySet()) {
            Shark shark = entry.getValue();

            int dist = shark.s;
            while (dist > 0) {
                int diff = 0;
                switch (shark.d) {
                    case 1:
                        diff = Math.min(shark.r, dist);
                        shark.r -= diff;
                        dist -= diff;
                        if (dist > 0)
                            shark.d = 2;
                        break;
                    case 2:
                        diff = Math.min(r - shark.r - 1, dist);
                        shark.r += diff;
                        dist -= diff;
                        if (dist > 0)
                            shark.d = 1;
                        break;
                    case 3:
                        diff = Math.min(c - shark.c - 1, dist);
                        shark.c += diff;
                        dist -= diff;
                        if (dist > 0)
                            shark.d = 4;
                        break;
                    case 4:
                        diff = Math.min(shark.c, dist);
                        shark.c -= diff;
                        dist -= diff;
                        if (dist > 0)
                            shark.d = 3;
                        break;
                }
            }

            if (copyMap[shark.r][shark.c] != 0) {
                Shark existShark = sharks.get(copyMap[shark.r][shark.c]);
                if (existShark.z > shark.z) removeList.add(entry.getKey());
                else {
                    removeList.add(copyMap[shark.r][shark.c]);
                    copyMap[shark.r][shark.c] = entry.getKey();
                }
            } else copyMap[shark.r][shark.c] = entry.getKey();
        }

        for (Integer integer : removeList) {
            sharks.remove(integer);
        }

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) map[i][j] = copyMap[i][j];
        }
    }

    private static void catchShark(int curC) {
        for (int i = 0; i < r; i++) {
            Shark shark = sharks.getOrDefault(map[i][curC], null);
            if (shark != null) {
                sharks.remove(map[i][curC]);
                res += shark.z;
                break;
            }
        }
    }
}

코드 설명

구현이 조금 귀찮은 문제였다.

 

문제에서 맵은 주어지지 않았지만 r x c의 맵을 만들었다.

그리고 각각의 상어들을 클래스로 두었고 HashMap을 이용해 저장했는데 key는 상어들의 고유 인덱스로 두었다.

맵에는 상어들의 위치를 인덱스로 표시했다.

 

중요 알고리즘은 catchShark와 moveShark함수에서 이루어진다.

catchShark는 낚시왕이 상어를 낚는 함수이고,

moveShark는 상어가 본인의 이동 방향, 속도대로 이동을 시켜주는 함수이다.

 

catchShark함수같은 경우 해당 행을 0부터 순회하며 상어를 만나면 해당 상어를 HashMap에서 삭제하고 끝내는 작업이라 간단했다.

moveShark에서 까다로운 것은 두가지였다.

1. 상어의 인덱스가 r, c를 넘어가면 반대방향으로 이동하는 것을 어떻게 처리할 것인가
2. 상어를 어떻게 삭제할 것인가

일단 1번을 해결한 코드다.

while (dist > 0) {
    int diff = 0;
    switch (shark.d) {
        case 1:
            diff = Math.min(shark.r, dist);
            shark.r -= diff;
            dist -= diff;
            if (dist > 0)
                shark.d = 2;
            break;
        case 2:
            diff = Math.min(r - shark.r - 1, dist);
            shark.r += diff;
            dist -= diff;
            if (dist > 0)
                shark.d = 1;
            break;
        case 3:
            diff = Math.min(c - shark.c - 1, dist);
            shark.c += diff;
            dist -= diff;
            if (dist > 0)
                shark.d = 4;
            break;
        case 4:
            diff = Math.min(shark.c, dist);
            shark.c -= diff;
            dist -= diff;
            if (dist > 0)
                shark.d = 3;
            break;
    }
}

간단하게, 해당 방향으로 남은 거리를 diff에 저장하고 dist에서 diff를 빼 남은 거리를 계산했다.

dist가 남았다면 방향을 180도 변경하여 다시 위 작업을 반복하면 된다.

 

2번 문제를 해결할 땐 두 가지 문제점이 더 있었다.

맵에 인덱스를 저장해놓고 상어의 여부를 판단하다보니 아직 움직이지 않은 상어를 삭제해버리는 상황이 발생했다.

그래서 초마다 새로운 맵을 만들고 덧붙이는 작업을 해주었다.

//moveShark 함수 내

for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) map[i][j] = copyMap[i][j];
}

 

그리고 HashMap을 이터레이터로 순회하며 상어의 이동 작업을 수행했는데 바로 삭제해버릴 경우 'ConcurrentModificationException'에러가 발생했다.

 

그래서 삭제 리스트를 새로 만들고 1초마다 이동이 끝나면 삭제 리스트에 있는 상어들을 제거해주는 작업을 했다.

private static void moveShark() {
    List<Integer> removeList = new ArrayList<>();

    for (Map.Entry<Integer, Shark> entry : sharks.entrySet()) {
        
        // ~상어 이동 작업~
        
        if (copyMap[shark.r][shark.c] != 0) {
            Shark existShark = sharks.get(copyMap[shark.r][shark.c]);
            if (existShark.z > shark.z) removeList.add(entry.getKey());
            else {
                removeList.add(copyMap[shark.r][shark.c]);
                copyMap[shark.r][shark.c] = entry.getKey();
            }
        } else copyMap[shark.r][shark.c] = entry.getKey();
    }

    for (Integer integer : removeList) {
        sharks.remove(integer);
    }
}