[백준] 16236 아기 상어 - 자바

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

16236번: 아기 상어

문제 풀이

주어진 보드에서 탐색을 통해 물고기를 얼마나 먹을 수 있는지 구하는 문제이다. 하지만 물고기를 먹는데 우선순위가 있다.

1. 가장 가까운 물고기를 먼저 먹는다
   1. 같은 거리라면 가장 위에 있는 물고기를 먹는다
   2. 같은 높이라면 왼쪽에 있는 먹이를 먹는다
2. 물고기의 크기가 아기 상어보다 작아야 한다.

이를 통해 각 물고기를 향하기 위한 우선순위 조건을 파악할 수 있고 우선순위 큐를 사용하여 해당조건에 맞는 탐색 방향을 정할 수 있다.

또한 탐색 순서는 up, left, right, down 순서가 될 것이다. 따라서 반복문으로 보드를 탐색할 때 해당 방향을 가지도록 dx, dy를 선언해주었다.

static int[] dx = {-1, 0, 0, 1};
static int[] dy = {0, -1, 1, 0};

이제 이 탐색 방향을 가지고 가장 가까운 물고기를 찾아 먹고 또 다른 물고기를 찾으러 가면 된다.

여기서 헷갈릴 수 있는 부분이 상어 입장에서 상어보다 낮은 사이즈의 물고기는 같은 가치를 가진다는 것이다. 즉, 상어 사이즈가 4일 때 사이즈 3인 물고기와 사이즈 1인 물고기는 똑같이 잡아 먹을 수 있는 동등한 가치의 물고기이다.

 

이제 탐색하기 위한 준비를 해보자. board와 위에서 언급한 우선순위를 만들었다.

class Shark {
    int x;
    int y;
    int move;

    public Shark(int x, int y, int move) {
        this.x = x;
        this.y = y;
        this.move = move;
    }
}

//main
board = new int[N][N];
Shark shark = null;

for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) {
        board[i][j] = sc.nextInt();
        if (board[i][j] == 9) {
            shark = new Shark(i, j, 0);
            board[i][j] = 0;
        }
    }

int size = 2;
int eat = 0; // 먹은 물고기 수
int totalMove = 0; // 움직인 총 거리
PriorityQueue<Shark> q = new PriorityQueue<>((s1, s2) -> {
    if (s1.move != s2.move) {
        return s1.move - s2.move;
    } else {
        if (s1.x != s2.x)
            return s1.x - s2.x;
        return s1.y - s2.y;
    }
});

 

첫 번째 while문을 통해 모든 물고기를 먹을 때까지 반복하고 두 번째 while문을 통해 가장 가까운 물고기를 찾아 나가는 것이다.

물고기를 먹었다는 뜻은 다른 물고기를 찾기 위해 기존에 있던 큐와 방문체크에 대해 새로 초기화 해주어야 한다.

while (true) { // 더 이상 먹을 물고기가 없으면 종료
    q.clear();
    boolean[][] visit = new boolean[N][N];

    q.add(new Shark(shark.x, shark.y, 0)); // y좌표, x좌표, 이동한 거리
    visit[shark.x][shark.y] = true;

    boolean eatFood = false; // 상어가 먹이를 먹었는지 체크할 변수

    while (!q.isEmpty()) { // 먹을 수 있는 물고기를 찾는다. 찾았다면 eatFood = true가 됨
        shark = q.poll();

        if (board[shark.x][shark.y] != 0 && board[shark.x][shark.y] < size) { // 먹이가 있으면서 상어의 사이즈보다 작다면?
            board[shark.x][shark.y] = 0; // 물고기를 제거
            eat++;
            totalMove += shark.move; // 움직인 거리를 총 움직인 거리에 추가
            eatFood = true; // 먹이 먹었다고 체크
            break;
        }

        for (int k = 0; k < 4; k++) {
            int nx = shark.x + dx[k];
            int ny = shark.y + dy[k];

            if (outOfBoard(nx, ny) || visit[nx][ny] || board[nx][ny] > size) {
                continue;
            }

            q.add(new Shark(nx, ny, shark.move + 1));
            visit[nx][ny] = true;
        }
    }

    if (!eatFood) // 물고기를 먹지 못했다면 더이상 먹을 물고기가 없다는 뜻
        break;

    if (size == eat) { // 사이즈와 먹이를 먹은 수가 동일하다면 상어의 크기를 증가
        size++;
        eat = 0;
    }
}

static boolean outOfBoard ( int x, int y){
    return x < 0 || y < 0 || x >= N || y >= N;
}

코드

import java.util.PriorityQueue;
import java.util.Scanner;

class Shark {
    int x;
    int y;
    int move;

    public Shark(int x, int y, int move) {
        this.x = x;
        this.y = y;
        this.move = move;
    }
}
public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int[][] board;
    static int N;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        board = new int[N][N];
        Shark shark = null;

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {
                board[i][j] = sc.nextInt();
                if (board[i][j] == 9) {
                    shark = new Shark(i, j, 0);
                    board[i][j] = 0;
                }
            }

        int size = 2;
        int eat = 0; // 먹은 물고기 수
        int totalMove = 0; // 움직인 총 거리

        while (true) {
            PriorityQueue<Shark> que = new PriorityQueue<>((s1, s2) -> {
                if (s1.move != s2.move) {
                    return s1.move - s2.move;
                } else {
                    if (s1.x != s2.x)
                        return s1.x - s2.x;
                    return s1.y - s2.y;
                }
            });

            boolean[][] visit = new boolean[N][N];

            que.add(new Shark(shark.x, shark.y, 0)); // y좌표, x좌표, 이동한 거리
            visit[shark.x][shark.y] = true;

            boolean eatFood = false; // 상어가 먹이를 먹었는지 체크할 변수

            while (!que.isEmpty()) {
                shark = que.poll();

                if (board[shark.x][shark.y] != 0 && board[shark.x][shark.y] < size) { // 먹이가 있으면서 상어의 사이즈보다 작다면?
                    board[shark.x][shark.y] = 0; // 물고기를 제거
                    eat++;
                    totalMove += shark.move; // 움직인 거리를 총 움직인 거리에 추가
                    eatFood = true; // 먹이 먹었다고 체크
                    break;
                }

                for (int k = 0; k < 4; k++) {
                    int nx = shark.x + dx[k];
                    int ny = shark.y + dy[k];

                    if (outOfBoard(nx, ny) || visit[nx][ny] || board[nx][ny] > size) {
                        continue;
                    }

                    que.add(new Shark(nx, ny, shark.move + 1));
                    visit[nx][ny] = true;
                }
            }

            if (!eatFood) // 큐가 비워질 때까지 먹이를 먹은적이 없다면, 더 이상 먹은 물고기가 없으므로 탈출
                break;

            if (size == eat) { // 사이즈와 먹이를 먹은 수가 동일하다면 상어의 크기를 증가
                size++;
                eat = 0;
            }
        }


        System.out.println(totalMove);

    }
    static boolean outOfBoard ( int x, int y){
        return x < 0 || y < 0 || x >= N || y >= N;
    }


}