[BOJ/Java] 16236: 아기 상어

문제

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

N x N 크기의 격자에 물고기 M마리와 아기 상어 1마리가 있다. 한 칸에는 물고기가 최대 한 마리만 존재한다.

물고기, 아기 상어는 모두 크기를 가지며 처음 아기 상어는 2의 크기로 시작하며 1초에 상하좌우로 인접한 칸으로 이동한다.

아기 상어는 자신보다 큰 물고기는 지나갈 수 없고, 나머지 칸은 지나갈 수 있다. 아기 상어는 자신보다 작은 물고기만 먹을 수 있다.

아기 상어는 다음과 같은 기준으로 이동한다.

• 더 이상 먹을 수 있는 물고기가 없다면 이동을 종료한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기로 간다.
  • 거리는 물고기 칸까지 지나야하는 칸의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위의 물고기, 그런 물고기가 많다면 가장 왼쪽 물고기를 먹는다.

아기 상어는 물고기가 있는 칸으로 이동과 동시에 먹는다. 물고기를 먹으면 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수를 먹을 때마다 크기가 1 증가한다.

아기 상어가 이동을 종료할 때까지 몇 초가 걸리는지 구해야 한다.

• 2 ≤ N ≤ 20
• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

 

풀이

먹을 수 있는 물고기까지 최소로 이동해야 하므로 BFS를 사용했다.

 

로직이 복잡하진 않다고 생각해 함수 하나에 상어의 모든 이동 로직을 작성했다. 모든 이동 시의 정보를 담기 위해 현재 위치, 크기, 먹은 물고기의 양, 이동한 거리를 담은 `Shark` 클래스를 정의했다. 먹을 수 있는 물고기를 선택하는 로직은 현재 위치에서 가장 가까운 물고기 중 가장 위(x 좌표가 작고), 그런 물고기가 여럿일 경우 가장 왼쪽(y 좌표가 작은) 물고기를 먼저 선택하므로, 우선순위  큐의 `Comparator` 객체로 해당 기준을 넣어 정렬한다.

 

모든 칸을 돌고 나면 먹을 수 있는 물고기 후보 중 하나를 먹고, 아기 상어의 상태를 업데이트해준다. 후보군이 없을 경우, 종료하며 지금까지 이동한 거리를 반환한다.

 

코드

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

public class Main {
    static int n;
    static int[][] map;
    static int[] dx = {-1, 0, 1, 0}; // 상, 좌, 하, 우
    static int[] dy = {0, -1, 0, 1};
    static class Shark {
        int r, c, size, eaten, dist;
        public Shark(int r, int c, int size, int eaten, int dist) {
            this.r = r;
            this.c = c;
            this.size = size;
            this.eaten = eaten;
            this.dist = dist;
        }
    }
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        // 아기 상어의 크기는 처음 2
        // 아기 상어는 자신보다 큰 물고기가 있는 칸을 제외하고 모두 지나갈 수 있다.
        // 자신보다 작은 물고기는 먹을 수 있다. 크기가 같은 경우 지나갈 수는 있지만 먹을 수는 없다.
        // 먹을 수 있는 물고기가 없으면 종료한다.
        // 먹을 수 있는 물고기가 1마리라면, 물고기를 먹으러
        // 더 많다면, 거리가 가장 가까운 물고기를 먹으러
        // 거리가 가까운 물고기가 많으면, 가장 위 물고기, 그러한 물고기가 여러 마리면 가장 왼쪽 물고기
        // 크기와 같은 수를 먹을 때마다 크기가 1씩 증가
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        int[] start = new int[2]; // 시작 위치
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                String info = st.nextToken();
                if (info.equals("9")) {
                    start[0] = i; start[1] = j;
                    map[i][j] = 0;
                    continue;
                }
                map[i][j] = Integer.parseInt(info);
            }
        }

        Shark shark = new Shark(start[0], start[1], 2, 0, 0);
        while (true) {
            Shark next = bfs(shark);
            if (next == null) break; // 먹을 수 있는 물고기가 없으면 종료한다.
            shark = next;
        }

        System.out.println(shark.dist);
    }

    static Shark bfs(Shark shark) {
        Queue<int[]> queue = new ArrayDeque<>();
        PriorityQueue<Shark> candidates = new PriorityQueue<>((a, b) -> {
            if (a.dist != b.dist) return a.dist - b.dist;
            if (a.r != b.r) return a.r - b.r;
            return a.c - b.c;
        });

        visited = new boolean[n][n];
        queue.add(new int[]{shark.r, shark.c, 0});
        visited[shark.r][shark.c] = true;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0], c = curr[1], dist = curr[2];

            if (map[r][c] != 0 && map[r][c] < shark.size) {
                candidates.add(new Shark(r, c, shark.size, shark.eaten, dist));
            }

            for (int i = 0; i < 4; i++) {
                int nr = r + dx[i];
                int nc = c + dy[i];

                if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                if (visited[nr][nc] || shark.size < map[nr][nc]) continue;

                visited[nr][nc] = true;
                queue.add(new int[]{nr, nc, dist + 1});
            }
        }

        if (!candidates.isEmpty()) {
            Shark target = candidates.poll();
            map[shark.r][shark.c] = 0;
            map[target.r][target.c] = 0;
            int newEaten = shark.eaten + 1;
            int newSize = shark.size;
            if (newEaten >= shark.size) {
                newSize++;
                newEaten = 0;
            }
            return new Shark(target.r, target.c, newSize, newEaten, shark.dist + target.dist);
        } else {
            return null;
        }
    }

}