[알고리즘] 백준 - 아기 상어

백준 - 아기 상어

내 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;


public class baekjoon_16236 {

    static int sharkSize = 2;
    static int sharkEat = 0;
    static int[] sharkPos = new int[2];
    static int N;
    static int[][] graph;
    static int time = 0;
    static boolean[][] visited;
    static int[] dx = new int[]{0, -1, 1, 0};
    static int[] dy = new int[]{-1, 0, 0, 1};
    static PriorityQueue<FishInfo> fishInfo = new PriorityQueue<>();


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

        N = Integer.parseInt(br.readLine());
        graph = new int[N][N];


        for (int i = 0; i < N; i++) {
            String[] inputs = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                graph[i][j] = Integer.parseInt(inputs[j]);
                if (graph[i][j] == 9) {
                    sharkPos[0] = i;
                    sharkPos[1] = j;
                }
            }
        }

        while (true) {
            visited = new boolean[N][N];
            fishInfo = lookForFish(sharkPos[0], sharkPos[1]); //잡아 먹은 위치로 갱신
            if (fishInfo.size() == 0) {
                break;
            }
            FishInfo fish = fishInfo.poll();
            //크기 갱신
            sharkEat += 1;
            if (sharkEat == sharkSize) {
                sharkSize += 1;
                sharkEat = 0;
            }

            //기존 상어 지점 없애기
            graph[sharkPos[0]][sharkPos[1]] = 0;
            //먹힌 물고기 위치로 상어 이동
            graph[fish.y][fish.x] = 9;
            sharkPos[0] = fish.y;
            sharkPos[1] = fish.x;
            //시간 갱신
            time += fish.distance;
        }
        System.out.println(time);
    }

    private static PriorityQueue<FishInfo> lookForFish(int startY, int startX) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startY, startX, 0});
        fishInfo = new PriorityQueue<>();
        visited[startY][startX] = true;

        while (!queue.isEmpty()) {
            int[] elements = queue.poll();
            int y = elements[0];
            int x = elements[1];
            int count = elements[2];

            if (graph[y][x] != 9 && graph[y][x] != 0) {
                if (graph[y][x] < sharkSize) {
                    fishInfo.add(new FishInfo(count, y, x));
                }
            }

            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (0 <= ny && ny < N && 0 <= nx && nx < N) {
                    if (!visited[ny][nx] && graph[ny][nx] <= sharkSize) {
                        visited[ny][nx] = true;
                        queue.add(new int[]{ny, nx, count + 1});
                    }
                }
            }
        }
        return fishInfo;
    }


    public static class FishInfo implements Comparable<FishInfo> {
        int distance;
        int y;
        int x;

        FishInfo(int distance, int y, int x) {
            this.distance = distance;
            this.y = y;
            this.x = x;
        }

        @Override
        public int compareTo(FishInfo o) {
            if (this.distance > o.distance) { //y 에 대해 오름차순
                return 1;
            } else if (this.distance == o.distance) {
                if (this.y > o.y) {
                    return 1;
                } else if (this.y == o.y) {
                    if (this.x > o.x) {
                        return 1;
                    }
                }
            }
            return -1;
        }
    }
}

처음 문제 설계를 잘못하여 시간을 많이 잃었다.

거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기,
그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

처음에는 dx와 dy의 순서를

    static int[] dx = new int[]{0, -1, 1, 0};
    static int[] dy = new int[]{-1, 0, 0, 1}; 
    //위, 왼, 오, 아래

이렇게 정의하여 문제가 풀릴 줄 알았다. 하지만 현재 위치를 기준으로 오른쪽으로 2칸 떨어진 곳에 대상 물고기가 있고, 왼쪽 아래에 물고기가 있다고 가정해보자. 그러면 가장 높은 곳인 오른쪽 2칸 물고기를 골라야하지만, 저 방향만으로 순서를 조절하면 왼쪽 아래 물고기를 고른다.

따라서 bfs를 돌리며 종료하는 것이 아니라 우선순위큐에 담아서 나중에 한번에 우선순위큐를 반환해야한다. 우선순위큐에는 당연히 거리, y, x를 기준으로 오름차순으로 정렬하게 만든다.

comparable에 대해 잘 몰라서 찾아봤다. 따로 정리를 해야겠다.