[Algorithm] 백준_17143 낚시왕

문제

R * C의 격자판에서 낚시왕이 1초에 한 열씩 이동하며 땅과 가장 가까운 상어를 잡습니다. 상어를 잡으면 해당 좌표의 상어는 사라지고, 남은 상어가 이동합니다. 상어는 속력과 방향, 크기를 가지고 있으며 1초동안 속력만큼의 칸을 이동합니다. 상어의 이동 칸이 격자판을 넘는 경우 방향을 바꿔 반대방향으로 이동하면 됩니다.
최종 이동 후 같은 칸에 상어가 2마리가 존재하게 되면, 크기가 작은 상어는 잡아먹힙니다.
낚시왕의 이동 -> 낚시 -> 상어 이동은 1초 동안 일어나게 되고, 최종적으로 낚시왕이 모든 열을 이동하면서 잡은 상어 크기의 합을 구하면 되는 문제입니다.

풀이

1. Shark 클래스를 만들어서 상어의 좌표와 속력, 방향, 크기를 저장합니다.
2. sharks 객체 리스트로 map에 있는 상어를 관리합니다.
3. map[r][c]에 상어를 저장합니다.
4. 열의 길이 c만큼 반복문을 돌면서 가장 가까운 상어를 낚습니다.
   getShark() r을 1씩 증가시키면서 map[r][c]의 값이 null이 아니면 상어를 잡습니다.
   잡고 break문으로 반복문을 빠져나옵니다. (가장 가까운 한 마리만 잡아야하니)
   잡을 때마다 잡은 상어의 좌표는 null로 변경, sharks에서도 제거합니다.
5. moveShark() 상어가 이동합니다.
   방향에 따라 case를 나눠서 좌표를 증감, 방향을 변경했습니다. 아직 map에서의 이동은 하지 않고, shark 객체에서만 좌표를 변경합니다. 변경 전에 해당 좌표를 null로 만들어서 비워둡니다.
6. eatShark() map으로 상어를 한 마리씩 넣어주는데, map의 해당 좌표가 null이면 shark를 넣어주고, 아니라면 크기를 비교해서 넣어줍니다. 잡아먹힌 상어는 sharks 객체 배열에서도 삭제합니다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOJ_17143 {
    static int r;
    static int c;
    static int shark_num;
    static int total_size = 0;
    static Shark[][] map;
    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());

        shark_num = Integer.parseInt(st.nextToken());

        if (shark_num == 0) {
            System.out.println(0);
            return;
        }

        map = new Shark[r + 1][c + 1];

        for (int i = 0; i < shark_num; i++) {
            String input = br.readLine();
            st = new StringTokenizer(input);

            int r = Integer.parseInt(st.nextToken()); //x
            int c = Integer.parseInt(st.nextToken()); //y
            int s = Integer.parseInt(st.nextToken()); //속력
            int d = Integer.parseInt(st.nextToken()); //방향
            int z = Integer.parseInt(st.nextToken()); //크기

            Shark shark = new Shark(r, c, z, s, d);
            map[r][c] = shark;
            sharks.add(shark);
        }

        for (int i = 1; i <= c; i++) {
            getShark(i);
            moveShark();
            eatShark();
        }

        System.out.println(total_size);
    }

    static void getShark(int col) {
        Shark temp = null;
        for (int i = 1; i <= r; i++) {
            if (map[i][col] != null) {
                temp = map[i][col];
                break;
            }
        }

        if (temp != null) {
            map[temp.x][temp.y] = null;
            total_size += temp.size;
            sharks.remove(temp);
        }
    }


    static void moveShark() {
        for (int i = 0; i < sharks.size(); i++) {
            Shark shark = sharks.get(i);
            map[shark.x][shark.y] = null;
            shark.go();
        }
    }

    static void eatShark() {
        for (int i = sharks.size() - 1; i >= 0; i--) {
            Shark s = sharks.get(i);
            if (map[s.x][s.y] == null) {
                map[s.x][s.y] = s;
            } else {
                if (map[s.x][s.y].size > s.size) {
                    sharks.remove(s);
                } else {
                    sharks.remove(map[s.x][s.y]);
                    map[s.x][s.y] = s;
                }
            }
        }
    }

    static class Shark {
        int x;
        int y;
        int size;
        int speed;
        int direction;

        public Shark(int x, int y, int size, int speed, int direction) {
            this.x = x;
            this.y = y;
            this.size = size;
            this.speed = speed;
            this.direction = direction;
        }

        public void go() {
            for (int i = 0; i < speed; i++) {
                switch (this.direction) {
                    case 1: // 위
                        if (x == 1) {
                            x++;
                            this.direction = 2;
                        } else {
                            x--;
                        }
                        break;
                    case 2: //아래:
                        if (x == r) {
                            x--;
                            this.direction = 1;
                        } else {
                            x++;
                        }
                        break;
                    case 3: //오른쪽
                        if (y == c) {
                            y--;
                            this.direction = 4;
                        } else {
                            y++;
                        }
                        break;
                    case 4: //왼쪽:
                        if (y == 1) {
                            y++;
                            this.direction = 3;
                        } else {
                            y--;
                        }
                        break;
                }
            }
        }
    }
}

회고

상어의 최종 이동을 하는데에 조금 오래 걸렸습니다. sharks 배열을 0부터 돌면 틀리고 거꾸로 돌리면 맞는데, 왜 맞는지 이해가 안 갑니다..

상어의 방향을 돌려주는 것을 case문으로 나눠서 풀었지만, 위 - 아래와 좌 - 우 이동을 묶어서 이동 거리를 계산하고 범위를 벗어나면 방향을 돌려주는 풀이도 있었습니다.