백준 알고리즘 - 아기상어

문제의 여러 조건들이 있는데 큰틀에서는 
먹이를 먹을 수 없을 때 까지 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;
            }
        }
    }
}

댓글

이 블로그의 인기 게시물

About JVM Warm up

About idempotent

About Kafka Basic

About ZGC

sneak peek jitpack

Spring Boot Actuator readiness, liveness probes on k8s

About Websocket minimize data size and data transfer cost on cloud

About G1 GC

대학생 코딩 과제 대행 java, python, oracle 네 번째