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

1. 문제설명

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있으며, 자신의 크기보다 작은 물고기만 먹을 수 있다. 크기가 같은 물고기는 먹을 수 없지만, 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

이동과 동시에 물고기를 먹고, 물고기를 먹으면, 그 칸은 빈 칸이 된다. 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구한다.

• 시간 제한: 2초
• 메모리 제한: 512MB

 

2. 접근 방식

• 아기 상어의 객체를 생성한다. (”현재 위치”, “현재 크기”, “먹은 물고기 수” 저장)
• BFS 탐색을 통해 물고기를 찾는다.
  • 상어가 이동할 수 있는 모든 경로를 탐색하면서, 먹을 수 있는 물고기를 찾는다. (자신보다 크기가 작은 물고기)
  • 상어가 먹을 수 있는 물고기를 발견하면, 해당 물고기는 우선순위 큐에 저장한다.
    • 우선순위 큐는 가장 가까운 물고기, y좌표가 작은 물고기, x좌표가 작은 물고기 순으로 정렬된다. (Fish 객체)
• 물고기 먹는 과정
  • BFS 탐색 후, 우선순위 큐에서 가장 우선순위 높은 물고기를 먹는다.
  • 물고기를 먹은 후, 상어의 위치와 이동 시간을 갱신하고, 상어가 먹은 물고기 수를 증가시킨다.
  • 물고기를 먹은 공간을 빈 칸(0)으로 설정한다.
  • 상어가 자신의 크기만큼 물고기를 먹으면 상어의 크기를 1 증가시킨다.
• 더 이상 먹을 수 있는 물고기가 없으면 BFS 메서드에서 null을 반환하여 탐색을 종료한다.
• 상어가 먹을 수 있는 물고기를 모두 먹었을 때, 총 걸린 시간을 출력한다.

 

3. 최종 코드

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

public class Main {
    static int n; // 공간 크기
    static int[][] space; // 물고기가 있는 공간 (물고기 크기 저장)
    static boolean[][] visited; // 방문 확인 배열
    static int time = 0; // 물고기 잡아먹는데 걸리는 시간
    static Shark shark = null;

    // 상좌하우 순서
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {1, 0, -1, 0};

    static class Shark {
        int[] pos; // 현재 위치
        int size; // 현재 크기
        int eaten; // 먹은 물고기 수

        public Shark(int[] pos, int size) { // 생성자
            this.pos = pos;
            this.size = size;
            this.eaten = 0;
        }
    }

    static class Fish implements Comparable<Fish> {
        int[] pos; // 현재 위치
        int time; // 아기상어가 먹으러 가는 시간

        public Fish(int[] pos, int time) { // 생성자
            this.pos = pos;
            this.time = time;
        }

        @Override
        public int compareTo(Fish o) {
            // 1. 먹으러 가는 시간이 짧은 순
            if (this.time != o.time) return Integer.compare(this.time, o.time);

            // 2. 가장 위에 있는 물고기 순 (y좌표가 작을수록 위)
            if (this.pos[0] != o.pos[0]) return Integer.compare(this.pos[0], o.pos[0]);

            // 3. 가장 왼쪽에 있는 물고기 순 (x좌표가 작을수록 왼쪽)
            return Integer.compare(this.pos[1], o.pos[1]);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        space = new int[n][n]; // 공간 초기화
        visited = new boolean[n][n]; // 방문 배열 초기화

        StringTokenizer st;
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                int fish = Integer.parseInt(st.nextToken());
                space[i][j] = fish; // 물고기 크기 저장
                if(fish == 9) { // 상어 현재 위치 찾으면
                    // 상어 객체 생성
                    shark = new Shark(new int[]{i, j}, 2);
                    space[i][j] = 0; // 상어의 위치는 빈 칸으로 설정
                }
            }
        }

        while(true) {
            Fish target = bfs(shark.pos); // 상어의 현재 위치에서 BFS 실행
            if(target == null) break; // 더 이상 먹을 물고기가 없으면 종료

            // 물고기 먹고 상어 위치 및 시간 갱신
            shark.pos = target.pos; // 상어 위치 갱신
            time += target.time; // 이동시간 추가
            shark.eaten++; // 먹은 물고기 수 증가
            space[target.pos[0]][target.pos[1]] = 0; // 물고기를 먹었으므로 공간을 빈칸으로 설정

            // 상어가 자신의 크기만큼 물고기를 먹었을 때 크기 증가
            if(shark.eaten == shark.size) {
                shark.size++;
                shark.eaten = 0; // 먹은 물고기 수 초기화
            }
        }

        System.out.println(time); // 총 걸린 시간
    }

    static Fish bfs(int[] pos) {
        PriorityQueue<Fish> fishQ = new PriorityQueue<>(); // 먹을 수 있는 물고기만 저장하는 우선순위 큐
        Queue<Fish> q = new LinkedList<>(); // 일반 BFS 탐색을 위한 큐
        q.add(new Fish(pos, 0));
        boolean[][] visited = new boolean[n][n];
        visited[pos[0]][pos[1]] = true;

        while(!q.isEmpty()) {
            Fish cur = q.poll();
            int[] curPos = cur.pos;
            int curTime = cur.time;

            // 상하좌우로 인접한 위치 탐색
            for(int i=0; i<4; i++) {
                int nx = curPos[0] + dx[i];
                int ny = curPos[1] + dy[i];

                // 다음 위치가 범위 안에 있고 아직 방문하지 않은 경우
                if(nx>=0 && nx<n && ny>=0 && ny<n && !visited[nx][ny]) {
                    // 아기 상어가 이동 가능한 경우
                    if(space[nx][ny] <= shark.size) {
                        visited[nx][ny] = true; // 방문 처리
                        q.add(new Fish(new int[]{nx, ny}, curTime + 1)); // 이동한 위치 추가

                        // 상어가 먹을 수 있는 물고기 (상어 크기보다 작은 경우)
                        if (space[nx][ny] > 0 && space[nx][ny] < shark.size) {
                            fishQ.add(new Fish(new int[]{nx, ny}, curTime + 1)); // 먹을 수 있는 물고기를 우선순위 큐에 추가
                        }
                    }
                }
            }
        }

        // 먹을 수 있는 물고기가 있으면 우선순위 큐에서 가장 우선순위가 높은 물고기를 반환
        if (!fishQ.isEmpty()) {
            return fishQ.poll(); // 가장 우선순위가 높은 물고기 반환
        }

        return null;
    }
}