[Java] BOJ/백준 16236번 아기 상어

[문제]

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

16236번: 아기 상어

 

 

[풀이]

문제에서 중요한 조건은 

1. 초기 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

2. if (아기 상어 크기 ≥ 물고기 크기) 아기 상어가 지나갈 수 있다.

3. if (아기 상어 크기 > 물고기 크기) 아기 상어가 물고기를 먹을 수 있다.

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

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

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

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

이렇게 6가지로 추릴 수 있을 것 같다.

 

아기 상어가 상하좌우로 1칸씩 이동할 수 있으며, 거리가 가장 가까운 물고기를 먹으러 가야 하기 때문에 bfs를 이용하는 문제라고 생각해 볼 수 있다.

 

1️⃣ 입력에서 아기 상어 위치 찾기

입력값을 이차원 배열인 space에 차례대로 넣어준다.

그 중 값이 아기 상어의 위치를 의미하는 9라면, queue에 아기상어의 위치와 최단 거리 값(현재는 아기 상어의 위치이므로 0)을 넣어준 후 해당 인덱스의 배열 값을 0으로 초기화한다.

 

2️⃣ 아기 상어가 먹을 수 있는 물고기까지의 최단 시간(거리) 구하기

bfs 함수에 현재 아기 상어의 위치가 담겨있는 큐와 아기 상어의 사이즈를 매개 변수로 전달하고 bfs 함수 내에는 먹을 수 있는 물고기를 담을 우선순위 큐를 초기화해 놓는다.

 

현재 아기 상어 위치에서 아직 방문하지 않은 상하좌우 칸 중 값이 0이거나, 물고기 크기가 아기 상어의 크기 이하인 경우 queue에 추가해 너비 우선 탐색을 한다.

탐색 중 물고기 크기가 아기 상어 크기 미만인 경우 함수 초기에 미리 선언해 놓은 pq에 담는다.

 

📌 헷갈릴까 봐

queue: 아기 상어가 먹을 수 있는 물고기까지의 최단 시간을 구하기 위한 탐색 큐

pq: 아기 상어가 먹을 수 있는 물고기를 우선순위대로 담아놓은 큐

 

📌 Shark 클래스는 문제의 사전 조건인
1. 거리가 가장 가까운 물고기를 먹기
2. 거리가 가까운 물고기가 많으면 가장 위에 있는 물고기 먹기
3. 그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기 먹기
의 우선순위를 지킬 수 있도록 Comparable 인터페이스의 compareTo 메서드를 오버라이드 했다.

 

3️⃣ 아기 상어가 먹을 수 있는 물고기로 이동

너비 우선 탐색을 마치면 pq에는 현재 크기의 상어가 먹을 수 있는 물고기가 우선순위대로 담겨있다.

 

따라서 첫 번째 물고기를 꺼내

1. 해당 space 배열 값을 0으로 수정한다.(물고기를 먹었으니까!)

2. 아기 상어가 먹은 물고기 수(cnt 변수)가 아기 상어 크기와 같으면, cnt를 0으로 초기화하고 아기 상어 크기를 1 늘린다.

3. 총 이동 시간을 담을 move 변수에 해당 물고기까지의 최단 시간을 더한다.

4. 아기 상어의 위치가 바뀌었기 때문에 queue를 다시 초기화하고 다시 현재 위치에서 다시 너비 우선 탐색을 진행한다.

이 과정을 반복한다.

 

만약 너비 우선 탐색을 마친 후 pq에 담긴 값이 없다면 아기 상어가 먹을 수 있는 물고기가 없다는 뜻이기 때문에 탐색을 종료한다.

 

[코드]

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

public class Main {

    static int N;
    static int[][] space;
    static PriorityQueue<Shark> pq = new PriorityQueue<>();
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static class Shark implements Comparable<Shark> {
        int x, y, distance;

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

        @Override
        public int compareTo(Shark o) {
            if (this.distance != o.distance) return Integer.compare(this.distance, o.distance);
            else {
                if (this.x == o.x) return Integer.compare(this.y, o.y);
                else return Integer.compare(this.x, o.x);
            }
        }
    }

    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];
        StringTokenizer st;
        Queue<Shark> queue = new LinkedList();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                space[i][j] = Integer.parseInt(st.nextToken());
                if (space[i][j] == 9) {
                    space[i][j] = 0;
                    queue.offer(new Shark(i, j, 0));
                }
            }
        }
        
        bfs(queue, 2);
        int move = 0, cnt = 0, sharkSize = 2;
        while (!pq.isEmpty()) {
            Shark now = pq.poll();
            space[now.x][now.y] = 0;
            if (++cnt == sharkSize) {
                cnt = 0;
                sharkSize++;
            }
            move += now.distance;
            queue = new LinkedList();
            queue.offer(new Shark(now.x, now.y, 0));
            bfs(queue, sharkSize);
        }
        System.out.println(move);

    }

    private static void bfs(Queue<Shark> queue, int sharkSize) {
        pq = new PriorityQueue<>();
        boolean visited[][] = new boolean[N][N];
        while (!queue.isEmpty()) {
            Shark now = queue.poll();

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

                if (nx < 0 || ny < 0 || nx >= N || ny >= N || space[nx][ny] > sharkSize || visited[nx][ny]) continue;
                visited[nx][ny] = true;
                queue.offer(new Shark(nx, ny, now.distance + 1));
                if (space[nx][ny] != 0 && space[nx][ny] < sharkSize) {
                    pq.offer(new Shark(nx, ny, now.distance + 1));
                }

            }
        }
    }
}