[Algo] 백준 16236 아기 상어 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/16236

메모리 : 19572KB

시간 : 184ms

언어 : Java 11

---

코드

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

public class Main {
    static class Node {
        int r, c, t;

        Node() {
        }

        Node(int r, int c, int t) {
            this.r = r;
            this.c = c;
            this.t = t;
        }
    }

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[][] map = new int[N][N];
        int babyx = 0;
        int babyy = 0;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 9) {
                    babyx = i;
                    babyy = j;
                    map[i][j] = 0;
                }
            }
        }
        int[] size = new int[10000];
        int sizeidx = 2;
        int time = 0;
        boolean[][] check;
        Queue<Node> q;
        PriorityQueue<Node> pq;

        // 먹을게없을때까지 반복
        while (true) {
            pq = new PriorityQueue<Node>(new Comparator<Node>() {

                     @Override
                public int compare(Main.Node o1, Main.Node o2) {
                    // 가까운 거리순 정렬
                    if (o1.t == o2.t) {
                        // 높이가 같고
                        if (o1.r == o2.r) {
                            // 좌측
                            return o1.c - o2.c;
                        } else {
                            return o1.r - o2.r;
                        }
                    }
                    return 0;
                }
            });
            check = new boolean[N][N];
            q = new LinkedList<>();
            q.add(new Node(babyx, babyy, 0));
            check[babyx][babyy] = true;
            while (!q.isEmpty()) {
                Node n = q.poll();
                for (int k = 0; k < 4; k++) {
                    int x = n.r + vector[k][0];
                    int y = n.c + vector[k][1];
                    if (x < N && y < N && x >= 0 && y >= 0 && !check[x][y]) {
                        if (map[x][y] == sizeidx || map[x][y] == 0) { // 같은 사이즈나 빈땅은 지나간다
                            q.add(new Node(x, y, n.t + 1));
                            check[x][y] = true;
                        } else if (map[x][y] < sizeidx) { // 작은사이즈는 먹는다
                            pq.add(new Node(x, y, n.t + 1));
                            check[x][y] = true;
                        }
                        // 큰 사이즈는 못지나간다
                    }
                }
            }
            // 먹을게 있다! 가장 가까운+상좌우하
            if (!pq.isEmpty()) {
                Node n = pq.poll();
                map[n.r][n.c] = 0;
                size[sizeidx]++;
                if (size[sizeidx] == sizeidx) {
                    sizeidx++;
                }
                time += n.t;
                babyx = n.r;
                babyy = n.c;
            } else {
                //엄마!
                break;
            }
        }
        System.out.println(time);
    }
}

풀이

1. 아기상어는 자기 몸 사이즈보다 작은 물고기를 먹을 수 있다. 가장 가까운 물고기- 그중에서도 상좌우하 순으로 먹어야 한다. 1칸 이동에 1초가 소요된다.
   • 가까운 물고기를 모두 찾기 위해 bfs로 바다를 탐색한다.
   • 지나가다가 만난 먹을 수 있는 물고기의 좌표를 모두 우선순위 큐에 담는다.
     • 우선순위 큐는 상좌우하로 정렬되어야 한다. 따라서 더 낮은 행 -> 같은 행일때 왼쪽 열 순서로 정렬한다.
     • 우선순위 큐에서 거리순으로 정렬되어있기 때문에 맨 위의 것을 꺼내먹으면 된다
2. 물고기를 사이즈만큼 먹으면 몸이 커진다. (size+=1)
3. 먹을 물고기가 없으면, pq에 담긴 먹이가 없으면 엄마를 부른다.

맨 처음에 bfs로 상좌우하 탐색하면 답이 나올줄 알았는데 생각처럼 되지 않았다. 우선순위 큐를 사용하면 메모리초과가 날 것 같아서 사용하지않았는데, 상좌우하탐색이 틀린 풀이었다ㅜㅜ 아직 왜 안되는지 알지못함...