BOJ (Java) 16236번: 아기 상어

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

 

---

풀이

물고기 크기 < 아기상어 크기 : 먹을 수 있음

빈 칸 / 물고기 크기 = 아기상어 크기 : 지나갈 수 있음

bfs로 다음 노드를 탐색하며 가장 가까우면서 위쪽, 왼쪽인 노드의 지점으로 이동

이 때 먹는 지점을 우선순위 큐를 사용해 탐색해야 한다.

bfs는 가장 위쪽, 왼쪽인 지점을 보장하지 못 함.

 

문제가 어렵진 않은데 이걸 몰라서 좀 헤맸다ㅠ

골드 3부터는 이런 작은 차이 하나가 답을 가르는 문제가 많아 더 노력해야겠다

---

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    private static int N;
    private static int size = 2;
    private static int[][] map;
    private static int[][] mv = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(bf.readLine());
        map = new int[N][N];
        int[] startLoc = new int[2];

        for (int i = 0; i < N; i++) {
            String[] inputs = bf.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(inputs[j]);
                if (map[i][j] == 9) {
                    startLoc[0] = i;
                    startLoc[1] = j;
                    map[i][j] = 0;
                }
            }
        }
        System.out.println(findMaxTime(startLoc, 0, 0));
    }

    private static int findMaxTime(int[] nowLoc, int eatCnt, int sec) {

        // 먹은 물고기 수 = 상어 크기 -> 상어 커짐
        if (eatCnt == size) {
            eatCnt = 0;
            size++;
        }

        // 다음에 갈 노드 확인
        int[] next = findNextLoc(nowLoc);
        if (next[0] == -1) {
            return sec;
        }

        // 먹은 곳 0으로 표기, 이동한 거리 더한 후 다음 노드 탐색
        map[next[0]][next[1]] = 0;
        sec += next[2];
        return findMaxTime(next, eatCnt + 1, sec);
    }

    // bfs로 탐색
    private static int[] findNextLoc(int[] nowLoc) {
        // 답이 될 수 있는 노드를 저장할 우선순위 큐
        // 거리, 높이, 좌우 순으로 정렬
        PriorityQueue<int[]> pq = new PriorityQueue<>(
                (a, b) -> {
                    if (a[2] == b[2]) {
                        if (a[0] == b[0]) {
                            return Integer.compare(a[1], b[1]);
                        }
                        return Integer.compare(a[0], b[0]);
                    }
                    return Integer.compare(a[2], b[2]);
                }
        );
        Queue<int[]> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[N][N];

        q.add(new int[]{nowLoc[0], nowLoc[1], 0});
        visited[nowLoc[0]][nowLoc[1]] = true;

        while (!q.isEmpty()) {
            int[] now = q.poll();

            for (int i = 0; i < 4; i++) {
                int x = now[0] + mv[i][0];
                int y = now[1] + mv[i][1];

                if (x < 0 || y < 0 || N <= x || N <= y || visited[x][y]) continue;

                if (map[x][y] == 0 || map[x][y] == size) {
                    q.add(new int[]{x, y, now[2] + 1});
                }
                // 답이 될 수 있다면 우선순위 큐에 삽입
                else if (map[x][y] < size) {
                    pq.add(new int[]{x, y, now[2] + 1});
                }
                visited[x][y] = true;
            }
        }

        // 우선순위 큐에 있는 값들 중 가장 높고 왼쪽의 값 반환
        if (pq.isEmpty()) {
            return new int[]{-1, -1, 0};
        }
        return pq.poll();
    }
}