[BJ] 16236 : 아기 상어

       문제 요약        

- 문제

- 아기상어 크기 : 2

 

- 아기상어 크기 변화 조건

자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가

 

- 상하좌우 인접 이동

자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있음

 

- 이동 우선순위

1. 거리가 가장 가까운 물고기

2. 가장 위에 있는 물고기

가장 왼쪽에 있는 물고기

 

 

- 입출력

 

         아이디어        

 

 

1. 가중치 없는 이동 거리 중 최단 거리 => bfs

2. 이동 우선 순위

3. 아기 상어 크기 변화 조건

이 3가지 정리를 잘 해야 한다.

2. 이동 우선 순위의 경우 직접 if문으로 구현해도 되지만, PriorityQueue를 사용하였다.

 

         소스코드        

 

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 B16236 {

    static int N;
    static int[][] board;
    static int dx[] = {-1, 0, 1, 0}; //위 왼 아래 오
    static int dy[] = {0, 1, 0, -1};
    static PriorityQueue<Node> fishes;
    static Queue<Node> move;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        board = new int[N][N];
        move = new LinkedList<>();
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] == 9) {
                    move.add(new Node(i, j, 0));
                    board[i][j] = 0;
                }
            }
        }

        int exp = 0;
        int time = 0;
        int sharkAge = 2;
        while (true) {
            fishes = new PriorityQueue<>();
            int[][] distance = new int[N][N];

            while (!move.isEmpty()) {
                Node current = move.poll(); // shark가 방문한 위치

                for (int i = 0; i < 4; i++) {
                    int nx = current.x + dx[i]; // 다음에 shark가 방문할 위치
                    int ny = current.y + dy[i];

                    if (nx >= 0 && nx < N && ny >= 0 && ny < N && distance[nx][ny] == 0 && board[nx][ny] <= sharkAge) {
                        distance[nx][ny] =
                                distance[current.x][current.y] + 1; // 다음에 shark 방문할 위치까지 움직인 거리 = 지금 위치까지 움직인 거리 + 1
                        move.add(new Node(nx, ny, distance[nx][ny]));  // 다음에 shark 가 방문할 위치
                        if (board[nx][ny] >= 1 && board[nx][ny] <= 6 && board[nx][ny] < sharkAge) {
                            fishes.add(new Node(nx, ny, distance[nx][ny])); // 물고기 위치
                        }
                    }
                }
            }

            if (fishes.size() == 0) { // 물고기가 존재하지 않는다면,
                System.out.println(time);
                return;
            }

            Node currentFish = fishes.poll(); // 잡아먹을 fish
            time += currentFish.dist; // 현재위치까지 거리
            exp++;
            board[currentFish.x][currentFish.y] = 0;
            if (exp == sharkAge) {
                sharkAge++;
                exp = 0;
            }
            move.add(new Node(currentFish.x, currentFish.y, 0));
        }
    }

    public static class Node implements Comparable<Node> {
        int x;
        int y;
        int dist;

        public Node(int x, int y, int dist) {
            super();
            this.x = x;
            this.y = y;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            if (this.dist == o.dist) {
                if (this.x == o.x) {
                    return this.y - o.y;
                }
                return this.x - o.x;

            }
            return this.dist - o.dist;
        }
    }
}