[BOJ] 백준 [16236] 아기 상어 JAVA

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

문제

풀이

상어 기준으로 bfs 탐색 시작하여 거리가 가장 가까운 물고기를 priorityQueue에 먼저 넣는다.
탐색이 끝났을 때 , 큐의 맨 앞에 있는것을 먹거나 물고기가 없을 경우엔 종료하면 끝.

 큐에 담는 이유
1. 거리가 가까운 순
2. 같은 거리에 있는 것이 여러개 있으면 좌표평면상 1.위쪽 -> 2.왼쪽 우선순위로 먹음.(이게 중요)
bfs 탐색으로 위,왼쪽을 먼저 하는게 아니라 문제조건에 좌표상 위,왼쪽에 있는것을 먼저 먹으라고 함

먹을때마다 움직인 거리만큼 시간늘려주고 , 먹은 수 카운트하면서, 상어 크기늘려주면 끝

 

import java.util.*;
import java.io.*;
 
public class Main{
 
    static Fish shark;
    static int[][] map;
    static int[] dx={0,-1,1,0},dy={-1,0,0,1};
    static int N,second;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for(int i=0;i<N;i++) {
            int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            map[i] = input;
            for(int j=0;j<N;j++) if(input[j]==9) shark = new Fish(j,i,2);
        }
        second=0;
 
        while (true){
            int[] result = search(shark.x, shark.y);
            if(result[2]==-1) break; // 더이상 먹이가 없을때
            shark.eatFish(new Fish(result[0],result[1],map[result[0]][result[1]]));
            second+=result[2]; //움직은 거리만큼 시간증가
        }
        System.out.println(second);
 
 
    }
    static int[] search(int x,int y){
        PriorityQueue<int[]> temp = new PriorityQueue<>(2, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[2]==o2[2]){
                    if(o1[1]==o2[1])
                        return o1[0]-o2[0];
                    return o1[1]-o2[1];
                }
                return o1[2]-o2[2];
            }
        });
        boolean[][] visit = new boolean[N][N];
        LinkedList<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x,y,0});
        visit[y][x] = true;
        while(!queue.isEmpty()){ // 0:x 1:y 2:cnt
            int[] cur = queue.poll();
            for(int i=0;i<dx.length;i++){
                int nextX = cur[0]+dx[i];
                int nextY = cur[1]+dy[i];
 
                if(!isRange(nextX,nextY)||visit[nextY][nextX]) continue;
 
                if(map[nextY][nextX]==0 || shark.size == map[nextY][nextX]){ // 한칸씩 이동
                    visit[nextY][nextX]=true;
                    queue.add(new int[]{nextX,nextY,cur[2]+1});
                }else if(shark.isEatable(nextX,nextY)) temp.add(new int[]{nextX,nextY,cur[2]+1}); //먹을 수 있는게 있으면 큐에 push
            }
        }
        if(!temp.isEmpty()) return temp.poll(); 
        return new int[]{0,0,-1}; //먹이가 없다면 cnt를 -1로 셋팅해서 리턴
    }
 
    static boolean isRange(int x,int y){
        return x>=0&&y>=0&&x<N&&y<N;
    }
 
    static class Fish {
        int x,y,size,exp;
 
        public Fish(int x, int y, int size) {
            this.x = x;
            this.y = y;
            this.size = size;
            this.exp=0;
        }
 
        public void eatFish(Fish fish){ // 물고기 먹기
            map[this.y][this.x]=0;
            this.y=fish.y;
            this.x=fish.x;
            this.exp++;
            if(this.size==this.exp){
                this.exp=0;
                this.size++;
            }
        }
        public boolean isEatable(int x,int y){ //먹을 수 있는지 검사
            return map[y][x] < this.size && map[y][x]!=0;
        }
    }
}