백준: 16236번 아기상어

🏆 문제 정보

문제 난이도 : 중상

문제 유형 : 시물레이션 / BFS

📌 문제

처음 아기상어 크기 ->2

상하좌우

 

크기가 같으면 이동 가능 . 잡아먹기는 불가능

잡아먹은 수만큼 크기가 커진다.

 

더 이상 먹을 게 없다면 stop

 

먹을 수 있는게 둘 이상이면,

거리 최소 -> 칸의 수

 

가장 위부터. 위가 똑같으면 왼쪽

📌 생각

1. 이동한 거리 -> BFS 이용

2. 로직

 

움직일 수 있으면 움직이고, 상하좌우로 이동할 때마다 count를 센다.

움직인 칸이 해당 shark의 size보다 작다면 eatList에 넣어준다.

 

eatList가 비어있다면 더이상 먹을 것이 없다는 것이므로 끝낸다.

eatList는 가장 가까운 기준, 가까운 것이 많다면 x 기준, x가 똑같다면 y기준이다.

그래서 Comparator와 PriorityQueue를 이용해서, 첫번째 값이 먹을 값이 되게 세팅한다.

 

첫번째 값이 먹을 값이므로, 해당 값으로 이동한다.

shark의 eatAmount를 1 증가시킨다.

---

그림을 먼저 생각하고 그림대로 그대로 구현하면 되는 문제다.

 

그림의 로직을 정확하게 세우는게 중요하다.

 

그리고 문제 정확하게 읽자. 해당 물고기 크기만큼 eatAmount를 늘려주는게 아니라, 해당 물고기의 크기가 어떻든 먹으면 +1증가인데, 해당 크기만큼 더해줘서 헤맸다.

 

로직이 맞는데 이상하게 나오는 것 같을 때는,

 

1. 로직 점검

2. 오타 점검

3. logging 으로 빠르게 넘어가자.

📌 코드

package src.backjoon.아기상어;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.*;

/**
 * date : 21.08.25
 */

public class Main {

    static int N;
    static int[][] map;
    static Shark shark;
    static Queue<int[]> q;
    static int count;

    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    static Queue<int[]> eatList;

    static boolean[][] v;

    static class Shark{
        int x;
        int y;
        int size;
        int eatAmount;
        public Shark(int x, int y, int size, int eatAmount) {
            this.x = x;
            this.y = y;
            this.size = size;
            this.eatAmount = eatAmount;
        }
    }

    static Comparator<int[]> comp = new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            int compare3 = Integer.compare(o1[2],o2[2]);
            if(compare3!=0){
                return compare3;
            }else{
                int compareX = Integer.compare(o1[0],o2[0]);
                if(compareX !=0){
                    return compareX;
                }else{
                    return Integer.compare(o1[1],o2[1]);
                }
            }
        }
    };

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream("./src/backjoon/아기상어/input.txt"));

        Scanner sc = new Scanner(System.in);
        int tempX=0;
        int tempY=0;
        N = sc.nextInt();
        map = new int[N][N];
        v = new boolean[N][N];
        count=0;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                int loc = sc.nextInt();
                if(loc == 9){
                   tempX = i;
                   tempY = j;
                   map[i][j] = 0;
                }else{
                    map[i][j] = loc;
                }
            }
        }
        shark = new Shark(tempX,tempY,2,0);
        q = new LinkedList<>();
        eatList = new PriorityQueue<>(comp);

        while(true){
//            System.out.println("shark 위치는 x = " + shark.x + "  y = " + shark.y);
//            System.out.println("count = " + count);
            q.offer(new int[]{shark.x,shark.y,0});
            v = new boolean[N][N];
            eatList.clear();
            while(!q.isEmpty()){
                int[] poll = q.poll();
                for(int i=0;i<4;i++){
                    int nx = poll[0] + dx[i];
                    int ny = poll[1] + dy[i];

                    if(!isOut(nx,ny) && !v[nx][ny]  && map[nx][ny] <= shark.size){
                        q.offer(new int[]{nx,ny,poll[2]+1});
                        if(map[nx][ny]!=0 && map[nx][ny] < shark.size){
                            eatList.offer(new int[]{nx,ny,poll[2]+1});
                        }
                        v[nx][ny] = true;
                    }
                }
            }
//            printEatList();
//            System.out.println("====");
            if(eatList.isEmpty()){
                System.out.println(count);
                break;
            }else{
                int[] eat = eatList.poll();
                shark.eatAmount += 1;
                if(shark.eatAmount == shark.size){
                    shark.size++;
                    shark.eatAmount =0;
                }
                count += eat[2];
                map[eat[0]][eat[1]] = 0;
                shark.x = eat[0];
                shark.y = eat[1];
            }
        }

    }

    private static void printEatList() {
        for(int[] a : eatList){
            System.out.println(Arrays.toString(a));
        }
    }

    static boolean isOut(int nx,int ny){
        return nx<0 || nx>=N || ny<0 || ny>=N;
    }
}