[백준] 16236. 아기상어 (그래프/Java)

[백준] 16236. 아기상어

비슷한 유형으로 [SWEA] 2382. 미생물 격리 문제를 추천!

 

📌 풀이 과정

처음 아기 상어 위치에서 BFS를 수행해 아기상어의 크기보다 작은 물고기를 찾는다.

1. 거리가 가장 가까운 물고기
2. 거리가 같다면 가장 위쪽에 위치한 물고기
3. 위쪽까지 같다면 가장 왼쪽에 위치한 물고기

현재 먹을 수 있는 물고기에 대한 탐색이 끝나면 아기상어는 이러한 우선순위로 물고기를 선택해야 하는데

우선순위에 따라 쉽게 선택하기 위해서 PriorityQueue를 사용한다.

 

다음으로, 물고기를 먹을 때마다 아기 상어의 물고기를 먹은 횟수를 증가시키고,

크기 조건이 맞다면 아기상어의 크기를 증가시킨다.

 

✨ 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * 16236. 아기상어
 * 메모리: 21168 KB
 * 시간: 156 ms
 */
public class Main {

    static int N, full, time;
    static int[][] map;
    static Fish baby;

    static class Fish implements Comparable<Fish>{
        int x, y, size, time;

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

        @Override
        public int compareTo(Fish o) {
            if(this.time != o.time) return this.time - o.time; // 1. 거리가 가장 가까운 물고기
            else {
                if(this.x != o.x) {
                    return this.x - o.x; // 2. 가장 위에 위치한 물고기
                }
                return this.y - o.y;  // 3. 가장 왼쪽에 위치한 물고기
            }
        }

    }

    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++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 9) {
                    map[i][j] = 0;
                    baby = new Fish(i, j, 2, 0);
                }
            }
        }

        full = 0; // 아기상어가 먹은 물고기 수
        time = 0; // 아기상어가 이동한 시간
        while(true) {
            if(!eatBabyFish()) break;
        }

        System.out.println(time);
    }

    private static boolean eatBabyFish() {
        boolean[][] visited = new boolean[N][N];
        int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        Queue<int[]> fishQ = new LinkedList<>();
        PriorityQueue<Fish> canEat = new PriorityQueue<>();

        fishQ.add(new int[] {baby.x, baby.y, 0});
        visited[baby.x][baby.y] = true;

        while(!fishQ.isEmpty()) {
            int[] cur = fishQ.poll();
            int x = cur[0];
            int y = cur[1];
            int depth = cur[2];

            if(0 < map[x][y] && map[x][y] < baby.size) {
                canEat.add(new Fish(x, y, map[x][y], depth)); // 먹을 수 있는 물고기 수집
                continue;
            }

            for(int i = 0; i < 4; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];

                if(nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny]) continue;
                if(map[nx][ny] > baby.size) continue; // 아기상어 보다 큰 물고기는 지나갈 수 없음
                visited[nx][ny] = true;
                fishQ.add(new int[] {nx, ny, depth+1});
            }
        }

        // 더이상 먹을 수 있는 물고기가 없다면 종료
        if(canEat.isEmpty()) return false;

        Fish fish = canEat.poll(); // 물고기 먹기
        full++;
        baby.x = fish.x;
        baby.y = fish.y;
        time += fish.time;
        map[fish.x][fish.y] = 0;

        if(full == baby.size) { // 아기상어 진화
            baby.size++;
            full = 0;
        }
        return true;

    }


}