[백준 16236] 아기 상어(Java)

문제 링크 : https://www.acmicpc.net/problem/16236

이 문제는 bfs와 문제의 조건을 하나씩 구현해나가면 풀 수 있습니다.

이 문제에서 가장 처리하기 어려웠던 부분은 같은 조건인 물고기가 여러 마리일 때 어떤 식으로 처리하는지에 관한 부분입니다. 저는 우선순위 큐를 커스텀하여 큐에 담기는 요소들의 정렬 기준을 설정하여 먹을 수 있는 물고기는 모두 큐에 넣고, 실제로 먹는 물고기는 큐에서 Poll한 값만을 먹는 방식으로 처리하였습니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

public class Main{
    static int N;
    static int[][] req = new int[21][21];
    static int res = 0;
    static Fish babyShark;
    static int[] dy = {-1,0,0,1};
    static int[] dx = {0,-1,1,0};

    static PriorityQueue<Fish> eatenFish = new PriorityQueue<>(new Comparator<Fish>() {
        @Override
        public int compare(Fish fish1, Fish fish2) {
            // 거리가 같다면
            if(fish1.dist == fish2.dist){
                // 높이가 같다면 가장 왼쪽의 물고기부터
                if(fish1.y == fish2.y) return fish1.x-fish2.x;
                    // 가장 위의 물고기부터
                else return fish1.y-fish2.y;
            }
            // 거리가 작은 순으로 정렬
            else return fish1.dist-fish2.dist;
        }
    });

    static void searchFish(){
        boolean[][] check = new boolean[21][21];
        check[babyShark.y][babyShark.x] = true;

        Queue<Fish> queue = new LinkedList<>();
        queue.add(babyShark);

        while(!queue.isEmpty()){
            Fish curr = queue.poll();

            // 상어 상하좌우로 이동
            for(int i=0;i<4;i++){
                int ny = curr.y + dy[i];
                int nx = curr.x + dx[i];
                if(ny<0 || ny>=N || nx<0 || nx>=N) continue;

                // 아직 지나가지 않은 공간일 경우
                int fishSize = req[ny][nx];
                if(!check[ny][nx]){
                    // 자기보다 크기가 작은 경우 먹은 물고기 리스트에 넣기
                    if(curr.size > fishSize && fishSize!=0){
                        eatenFish.add(new Fish(ny,nx,fishSize,0,curr.dist+1));
                        check[ny][nx] = true;
                        queue.add(new Fish(ny,nx, curr.size, curr.eatNum, curr.dist+1));
                    }

                    // 크기가 같은 경우 또는 빈칸인 경우 큐에 추가
                    if(curr.size == fishSize || fishSize==0){
                        check[ny][nx] = true;
                        queue.add(new Fish(ny,nx, curr.size, curr.eatNum, curr.dist+1));
                    }
                }
            }
        }

    }

    static void eatFish(){
        // 먹을 수 있는 물고기 큐에서 가장 앞의 물고기만 가져옴
        Fish fish = eatenFish.poll();

        // 물고기 위치 및 상어 위치 초기화
        babyShark.y = fish.y;
        babyShark.x = fish.x;
        req[fish.y][fish.x] = 0;

        // 상어 먹은 횟수 증가
        babyShark.eatNum++;

        // 상어가 먹은 횟수와 크기가 같다면 사이즈 증가 후 먹은 횟수 초기화
        if(babyShark.eatNum == babyShark.size){
            babyShark.size++;
            babyShark.eatNum=0;
        }

        // 상어 이동 거리 누적
        res += fish.dist;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                req[i][j] = Integer.parseInt(st.nextToken());

                // 아기 상어 위치 체크
                if(req[i][j]==9){
                    babyShark = new Fish(i,j,2,0,0);
                    req[i][j] = 0;
                }
            }
        }

        while(true){
            // 먹은 물고기 초기화
            eatenFish.clear();
            // 먹을 수 있는 물고기 탐색
            searchFish();
            // 먹을 수 있는 물고기가 없다면 상어가 이동한 거리 리턴
            if(eatenFish.isEmpty()) break;
            // 먹을 수 있는 물고기 있다면 물고기 먹기
            else eatFish();
        }
        System.out.println(res);
    }
}

class Fish{
    int y;
    int x;
    int size;
    int eatNum;
    int dist;

    Fish(int y, int x, int size, int eatNum, int dist){
        this.y = y;
        this.x = x;
        this.size = size;
        this.eatNum = eatNum;
        this.dist = dist;
    }
}