백준 알고리즘 - 아기상어

문제의 여러 조건들이 있는데 큰틀에서는 

먹이를 먹을 수 없을 때 까지 BFS를 돌린다.

하지만 곤란했던 조건은 아래 조건이다.

1. 거리가 같은 먹이의 경우 y, x 값이 작은 먹이를 먹는다.

ex) 3 * 3

1 0 1

0 9 0

1 0 1 

의 경우 거리 2의 먹이는

(0,0), (0,2), (2,0) , (2,2) 총 4개

거리가 모두 2인 경우 y값과 제일 작은 먹이는 

(0,0) , (0,2) 총 2개

이 경우 x값이 제일 작은 먹이를 먹는다.

바로 (0,0)을 먹는다.

내가 시도한 방법.

현재 아기상어 사이즈에서 먹을 수 있는 모든 먹이를 거리 순으로 우선순위 큐에 넣는다.

거리가 제일 가까운 먹이들을 우선순위큐에서 꺼내면서 다시 리스트에 담는다.

거기서 y, x축이 제일 작은 먹이를 골라서 먹인다.

import java.util.*;

public class Main {

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

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

    static int N;

    static Queue<Graph> queue = new LinkedList<>();

    static class Pair implements Comparable<Pair>{

        int y;

        int x;

        int distance;

        public Pair(int y, int x, int distance) {

            this.y = y;

            this.x = x;

            this.distance = distance;

        }

        @Override

        public int compareTo(Pair o) {

            if (this.distance < o.distance) {

                return -1;

            } else if (this.distance > o.distance) {

                return 1;

            }

            return 0;

        }

    }

    static class Graph {

        Pair root;

        LinkedList<Pair> adj;

        public Graph(int y , int x, int distance, int size, int[][] area){

            this.root = new Pair(y, x, distance);

            this.adj = new LinkedList<>();

            for (int i = 0; i < 4; i++) {

                if ((-1 < y + dy[i] && y + dy[i] < N) && (-1 < x + dx[i] && x + dx[i] < N)

                        && area[y+dy[i]][x+dx[i]] <= size)

                    this.adj.add(new Pair(y + dy[i], x + dx[i], distance + 1));

            }

        }

    }

    static class BabyShark {

        int y;

        int x;

        int eatCnt;

        int size;

        int moveCnt;

    }

    public static void main(String[] args) {

        BabyShark babyShark = new BabyShark();

        Scanner scn = new Scanner(System.in);

        N = scn.nextInt();

        int[][] area = new int[N][N];

        boolean[][] visited = new boolean[N][N];

        for (int i = 0; i < area.length; i++) {

            for (int j = 0; j < area.length; j++) {

                area[i][j] = scn.nextInt();

                if (area[i][j] == 9) {

                    babyShark.y = i;

                    babyShark.x = j;

                    babyShark.size= 2;

                    babyShark.eatCnt = 0;

                }

            }

        }

        scn.close();

        while (true) {

            int mealCnt = BFS(babyShark, area, visited);

            if (mealCnt == 0)

                break;

        }

        System.out.println(babyShark.moveCnt);

    }

    private static int BFS(BabyShark babyShark, int[][] area, boolean[][] visited) {

        queue.offer(new Graph(babyShark.y, babyShark.x, 0, babyShark.size, area));

        visited[babyShark.y][babyShark.x] = true;

        PriorityQueue<Pair> pq = new PriorityQueue<>();

        while (!queue.isEmpty()) {

            Graph temp = queue.poll();

            for (int i = 0; i < temp.adj.size(); i++) {

                if (visited[temp.adj.get(i).y][temp.adj.get(i).x])

                    continue;

                visited[temp.adj.get(i).y][temp.adj.get(i).x] = true;

                if (area[temp.adj.get(i).y][temp.adj.get(i).x] != 0 && area[temp.adj.get(i).y][temp.adj.get(i).x] < babyShark.size)

                    pq.offer(temp.adj.get(i));

                queue.offer(new Graph(temp.adj.get(i).y, temp.adj.get(i).x, temp.adj.get(i).distance, babyShark.size, area));

            }

        }

        int mealCnt = pq.size();

        ArrayList<Pair> meals = new ArrayList<>();

        int shortestDis = 100;

        while (!pq.isEmpty()) {

            Pair temp = pq.poll();

            if (shortestDis >= temp.distance) {

                shortestDis = temp.distance;

                meals.add(temp);

            }

        }

        if (meals.size() > 0) {

            Pair meal = meals.get(0);

            for (int i = 1; i < meals.size(); i++) {

                if (meals.get(i).y < meal.y) {

                    meal = meals.get(i);

                } else if (meals.get(i).y == meal.y) {

                    if (meals.get(i).x < meal.x)

                        meal = meals.get(i);

                }

            }

            if (null != meal)

                haveMeals(meal, babyShark, area);

        }

        pq.clear();

        resetVisit(visited);

        return mealCnt;

    }

    private static void haveMeals(Pair meal, BabyShark babyShark, int[][] area) {

        babyShark.moveCnt += meal.distance;

        area[babyShark.y][babyShark.x] = 0;

        area[meal.y][meal.x] = 9;

        babyShark.y = meal.y;

        babyShark.x = meal.x;

        babyShark.eatCnt += 1;

        if (babyShark.eatCnt == babyShark.size) {

            babyShark.size += 1;

            babyShark.eatCnt = 0;

        }

    }

    private static void resetVisit(boolean[][] visit) {

        for (int i = 0; i < visit.length; i++) {

            for (int j = 0; j < visit.length; j++) {

                visit[i][j] = false;

            }

        }

    }

}