[BOJ] 아기 상어(16236)

[백준(BOJ)] 16236_아기 상어 JAVA

문제 : BOJ_16236번 아기 상어

문제 설명

아기 상어가 상하좌우로 움직이면서 물고기를 먹습니다.

이때 물고기는 아기 상어의 크기보다 작은 물고기만 먹을 수 있고, 상어의 크기보다 큰 물고기가 있는 곳은 지나갈 수 없습니다.

가장 가까운 거리에 있는 먹을 수 있는 물고기부터 먹는데, 같은 거리에 있는 물고기가 여러 물고기라면 위 다음 왼쪽에 있는 물고기부터 먹습니다.

또 한 자기의 몸 크기 수만큼의 물고기를 먹으면 몸의 크기가 1 증가합니다.

이러한 조건에서 물고기가 한 번 이동하는 시간을 1초라고 할 때 물고기가 먹을 수 있는 모든 물고기를 먹는데 걸리는 시간을 출력해야 합니다.

---

Solution

bfs, 완전 탐색

우선 bfs로 상어의 위치부터 시작해 도달할 수 있는 모든 곳에 도달하여 먹을 수 있는 물고기를 확인합니다.

확인한 물고기를 우선순위 큐에 넣어가며 정렬하는데, 이때 정렬의 기준은 물고기의 크기, 물고기의 세로 좌표, 물고기의 가로 좌표 순서로 정렬합니다.

우선순위 큐에 들어있는 첫 번째 물고기의 크기가 상어의 몸 크기 보다 작다면 그것을 먹은 걸로 처리하고 다시 bfs를 진행해 줍니다.

N의 크기가 20이므로 이와 같은 방법으로 섭취할 수 있는 모든 물고기를 섭취하게 하면 정답을 출력할 수 있습니다.

---

Description

• 세 가지 요소를 기준으로 물고기를 정렬해야 하기 때문에, Comparable을 이용하여 Fish라는 클래스를 만들었습니다.
• 물고기를 섭취하면 그 자리가 0이 되는 것, 상어의 몸 크기 수만큼 섭취하면 상어의 몸이 증가하는 것, 처음 상어 위치 좌표에 할당된 값은 9인 것 등 놓칠 수 있는 조건들을 잘 따져서 실수를 없애가며 풀어야 합니다.

---

import java.io.*;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

class Fish implements Comparable<Fish>{
    private int x;
    private int y;
    private int value;

    public Fish(int x, int y, int value){
        this.x = x;
        this.y = y;
        this.value = value;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getValue() {
        return value;
    }

    @Override
    public int compareTo(Fish other) {
        if(this.value==other.value && this.x == other.x) return Integer.compare(this.y, other.y);
        else if(this.value == other.value) return Integer.compare(this.x, other.x);
        else return Integer.compare(this.value, other.value);
    }
}

class Pair{
    private int x;
    private int y;

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
    public Pair(int x,int y){
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static int n, cnt, sharkSize=2, nowEat;
    public static int[][] map;
    public static int nowX, nowY;
    public static int[] dx = {-1,1,0,0};
    public static int[] dy = {0,0,-1,1};
    public static boolean bfs(){
        PriorityQueue<Fish> pq = new PriorityQueue<>();
        int[][] vis = new int[n+1][n+1];
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                vis[i][j]=-1;
            }
        }
        Queue<Pair> q = new LinkedList<>();
        q.offer(new Pair(nowX,nowY));
        vis[nowX][nowY] = 0;
        while(!q.isEmpty()){
            Pair pair = q.poll();
            int x = pair.getX();
            int y = pair.getY();
            for(int i=0;i<4;i++){
                int nx = x+dx[i];
                int ny = y+dy[i];
                if(nx<1||ny<1||nx>n||ny>n) continue;
                if(vis[nx][ny]!=-1) continue;
                if(map[nx][ny]> sharkSize) continue;
                vis[nx][ny] = vis[x][y]+1;
                q.offer(new Pair(nx,ny));
                if(map[nx][ny]>0 && map[nx][ny]<sharkSize)  pq.offer(new Fish(nx,ny,vis[nx][ny]));
            }
        }
        if(pq.isEmpty()) return false;
        else {
            Fish fish = pq.poll();
            int nx = fish.getX();
            int ny = fish.getY();
            nowEat++;
            cnt+=vis[nx][ny];
            map[nx][ny] = 0;
            nowX = nx;
            nowY = ny;
            if(nowEat==sharkSize) {
                sharkSize++;
                nowEat = 0;
            }
            return true;
        }
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        map = new int[n+1][n+1];
        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j]==9){
                    nowX = i;
                    nowY = j;
                    map[i][j]=0;
                }
            }
        }
        while (true){
            if(!bfs()) break;
        }
        bw.write(String.valueOf(cnt));
        bw.flush();
        br.close();
        bw.close();
    }
}