[Baekjoon] 16236 아기상어

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

i) 여기서 N은 3이고, 물고기는 0마리 입니다.

ii) 아기 상어는 숫자 9입니다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

i) 입력이 다음과 같을 때 물고기는 총 8마리 입니다.

ii) 각각의 숫자는 물고기의 크기를 나타냅니다

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

Java
복사

i) 위와 같은 입력이 주어졌을 때 상어는 움직일 수 없습니다. 상하좌우가 다 초기의 상어 크기 (2) 보다 높기 때문입니다.

Java
복사

i) 위와 같은 입력이 주어졌을 때 상어는 먹을 물고기가 없습니다. 상어는 자신의 크기보다 작은 물고기만 먹을 수 있기 때문입니다. (즉, 초기 상어 크기가 2일 때 크기가 1인 물고기만 먹을 수 있음)

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

•

더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다. → 종료된다

•

먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. 

→ 먹을 수 있는 물고기를 어떻게 판별할까?

•

먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 

◦

거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.

◦

거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

→ 어떻게 구현할까?

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

즉,몇 칸을 움직여서 먹을 수 있는 물고리를 다 먹을 수 있는지 구하는 문제

조건 1. 먹을 수 있는 물고기는 먹는다.

조건 2. 먹을 수 있는 물고기가 두 마리 이상이면 다음과 같은 우선순위를 갖는다

거리가 짧은 순

위에 있는 물고기

왼쪽에 있는 물고기 

조건 3. 먹을 수 있는 물고기는 자기 보다 작은 물고기 이며, 자신의 크기 (예를 들어 상어의 크기가 3일 때, 3 마리를 먹어야 상어의 크기가 4가 됨)

package baekjoon.graph;

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

public class _16236 {
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {-1, 0, 1, 0};
    static int[][] board;
    static boolean[][] ch;
    static int LV;
    static int sharkX, sharkY;

    static PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            int compareDist = o1[2] - o2[2];
            if (compareDist != 0) {
                return compareDist;
            }

            int compareY = o1[0] - o2[0];
            if (compareY != 0) {
                return compareY;
            }

            return o1[1] - o2[1];
        }
    });

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

        // Intialization
        int N = Integer.parseInt(br.readLine());
        board = new int[N][N];
        LV = 2;

        for (int i = 0; i < board.length; i++) {
            String[] s = br.readLine().split(" ");
            for (int j = 0; j < board[i].length; j++) {
                board[i][j] = Integer.parseInt(s[j]);
                if (Integer.parseInt(s[j]) == 9) {
                    sharkX = j;
                    sharkY = i;
                    board[i][j] = 0; // Key 1
                }
            }
        }

        int totalCnt = 0; // 총 거리
        int fishCnt = 0; // 레벨 업에 필요한 fish 수
        while (ValidateAvaliableFish()) {
            int[] fish = pq.poll();
            fishCnt++;
            totalCnt += fish[2];
            board[fish[0]][fish[1]] = 0;
            sharkY = fish[0];
            sharkX = fish[1];
            if (fishCnt == LV) {
                fishCnt = 0;
                LV++;
            }
            pq.clear(); // Key 4
        }
        System.out.println(totalCnt);
        br.close();
    }

    public static boolean ValidateAvaliableFish() {
        boolean isTrue = false;
        Queue<int[]> q = new LinkedList<>(); // Key 2
        q.add(new int[]{sharkY, sharkX, 0}); 
        ch = new boolean[board.length][board[0].length];

        while (!q.isEmpty()) {
            int[] temp = q.poll();
            int Y = temp[0];
            int X = temp[1];
            int dist = temp[2];
            if (board[Y][X] != 0 && board[Y][X] < LV) { // Key 5
                isTrue = true;
                pq.add(new int[]{Y, X, dist});
            }
            for (int i = 0; i < 4; i++) { 
                int tempY = Y + dy[i];
                int tempX = X + dx[i];
                if (tempY < board.length && tempY >= 0 && tempX < board[0].length && tempX >= 0) {
                    if (ch[tempY][tempX] == false && board[tempY][tempX] <= LV) {
                        ch[tempY][tempX] = true;
                        q.add(new int[]{tempY, tempX, dist + 1}); // Key 3
                    }
                }
            }
        }
        return isTrue;
    }
}
Java
복사