[골드3, BFS+PQ] 백준 16236 - 아기 상어 (자바)

Think

1. 물고기를 어떤 자료구조로 관리할지, 상어기준으로 물고기와의 거리를 어떻게 계산할지, 먹는 우선순위를 어떻게 구분할지에 대해서 먼저 고민하고 시작했다.
2. 물고기는 Fish라는 클래스를 만들고 LinkedList로 관리 / 상어와 물고기와의 거리는 BFS를 통해 계산 (한번 먹을때마다 다시 계산) / 우선순위는 Fish 클래스에 Comparable을 통해 정렬시키기 - 를 통해 구현했다
3. 물고기 먹는 순서와 상어가 갇혔을때의 경우를 고려하지못해서 약간 정체됐지만, 그래도 풀었다.
4. 188ms로 통과했길래 다른 사람은 얼마나 걸렸는지 봤는데 84ms로 통과한 사람이 있어서 풀이를 구경했다.
5. 나는 상어가 물고기를 먹을때마다 물고기와의 거리를 계속 BFS를 통해 계산했는데, 이 사람은 BFS 한번만으로 풀어냈다. 그 아이디어는 우선순위 큐였다.
6. https://jouureee.tistory.com/88 를 참고하여 풀이를 이해했다.

 

 

내 정답코드 (BFS 한번 + PQ 활용)

import java.util.*;
import java.io.*;

public class test {
    static int N, maxSecond;
    static int[][] map;
    static boolean[][] isVisited;
    static Shark shark;
    static int[] dr = new int[]{0, 0, 1, -1};
    static int[] dc = new int[]{1, -1, 0, 0};
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        init();

        process();

        System.out.println(maxSecond);
    }

    private static void process() {
        bfsAndEatFish();
    }

    private static void bfsAndEatFish() {

        Queue<int[]> q = new LinkedList<>();
        isVisited = new boolean[N][N];

        q.add(new int[]{shark.r, shark.c});
        isVisited[shark.r][shark.c] = true;

        PriorityQueue<Fish> pq = new PriorityQueue<>();
        int distance = 0;

        while(!q.isEmpty()){
            int qSize = q.size();

            for (int i = 0; i < qSize; i++) {
                int[] sharkPosition = q.poll();

                for (int j = 0; j < 4; j++) {
                    int mr = sharkPosition[0] + dr[j];
                    int mc = sharkPosition[1] + dc[j];

                    if(mr < 0 || mc < 0 || mr >= N || mc >= N || isVisited[mr][mc]) continue;

                    if(map[mr][mc] != 0 && map[mr][mc] < shark.size){
                        pq.add(new Fish(mr,mc,map[mr][mc]));
                    }
                    if(map[mr][mc] <= shark.size){
                        q.add(new int[]{mr,mc});
                        isVisited[mr][mc] = true;
                    }
                }
            }

            distance++;

            if(!pq.isEmpty()){
                Fish fish = pq.poll();
                shark.countEattingFish++;
                map[fish.r][fish.c] = 0; //물고기 먹었으니 그 자리는 0으로 만들기

                if(shark.countEattingFish == shark.size){
                    shark.size++;
                    shark.countEattingFish = 0;
                }

                maxSecond += distance; // 물고기 위치까지 간 시간 더해주기
                distance = 0;
                pq.clear();
                q.clear();
                isVisited = new boolean[N][N];
                q.add(new int []{fish.r, fish.c});
                isVisited[fish.r][fish.c] = true;
            }
        }
    }

    private static void init() throws IOException {

        N = Integer.parseInt(br.readLine());

        map = new int[N][N];

        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) {
                    shark = new Shark(i, j, 2, 0);
                    map[i][j] = 0;
                }
            }
        }
    }

    public static class Fish implements Comparable<Fish> {
        int r;
        int c;
        int size;

        public Fish(int r, int c, int size) {
            this.r = r;
            this.c = c;
            this.size = size;
        }

        @Override
        public int compareTo(Fish o) {
            int res = 0;

            if (this.r == o.r) {
                res = this.c - o.c;
            } else {
                res = this.r - o.r;
            }
            return res;
        }

    }

    public static class Shark {
        int r;
        int c;
        int size;
        int countEattingFish;

        public Shark(int r, int c, int size, int countEattingFish) {
            this.r = r;
            this.c = c;
            this.size = size;
            this.countEattingFish = countEattingFish;
        }
    }

}

 

내 정답코드 (물고기 먹을때마다 BFS)

import java.util.*;
import java.io.*;

public class test {
    static int N, maxSecond;
    static int[][] map;
    static int[][] distanceMap;
    static boolean[][] isVisited;
    static Shark shark;
    static LinkedList<Fish> fish = new LinkedList<>();

    static int[] dr = new int[]{0, 0, 1, -1};
    static int[] dc = new int[]{1, -1, 0, 0};
    static StringBuilder sb = new StringBuilder();
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        init();

        process();

        System.out.println(maxSecond);
    }

    private static void process() {

        while(fish.size() != 0){
            calculateDistance();

            int index = -1;
            for (int i = 0; i < fish.size(); i++) {
                if(fish.get(i).size < shark.size && fish.get(i).distanceToShark != Integer.MAX_VALUE) {
                    index = i;
                    break;
                }
            }

            if(index == -1 ) break;
            Fish f = fish.remove(index);

            map[shark.r][shark.c] = 0;
            shark.r = f.r;
            shark.c = f.c;
            map[f.r][f.c] = 9;
            shark.countEattingFish++;
            maxSecond += f.distanceToShark;

            if(shark.countEattingFish == shark.size){
                shark.size++;
                shark.countEattingFish = 0;
            }
        }
    }

    private static void calculateDistance() {

        Queue<int[]> q = new LinkedList<>();
        isVisited = new boolean[N][N];
        distanceMap = new int[N][N];

        q.add(new int[]{shark.r, shark.c});
        isVisited[shark.r][shark.c] = true;
        distanceMap[shark.r][shark.c] = 0;

        while(!q.isEmpty()){
            int[] position = q.poll();

            for (int i = 0; i < 4; i++) {
                int mr = position[0] + dr[i];
                int mc = position[1] + dc[i];

                if(mr < 0 || mc < 0 || mr >= N || mc >= N || isVisited[mr][mc]) continue;
                if(map[mr][mc] > shark.size)    continue;

                distanceMap[mr][mc] = distanceMap[position[0]][position[1]] + 1;
                q.add(new int[]{mr,mc});
                isVisited[mr][mc] = true;
            }
        }

        for(Fish f : fish){
            if(distanceMap[f.r][f.c] == 0){
                f.distanceToShark = Integer.MAX_VALUE;
            }else{
                f.distanceToShark = distanceMap[f.r][f.c];
            }
        }

        Collections.sort(fish);
    }

    private static void init() throws IOException {

        N = Integer.parseInt(br.readLine());

        map = new int[N][N];

        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) {
                    shark = new Shark(i, j, 2, 0);
                } else if (map[i][j] != 0) {
                    Fish f = new Fish(i, j, map[i][j]);
                    fish.add(f);
                }
            }
        }
    }

    public static class Fish implements Comparable<Fish> {
        int r;
        int c;
        int size;
        int distanceToShark;

        public Fish(int r, int c, int size) {
            this.r = r;
            this.c = c;
            this.size = size;
        }

        @Override
        public int compareTo(Fish o1) {
            int res = 0;

            if (this.distanceToShark != o1.distanceToShark) {
                res = this.distanceToShark - o1.distanceToShark;
            }else if (this.r != o1.r) {
                res = this.r - o1.r;
            } else {
                res = this.c - o1.c;
            }
            return res;
        }

    }

    public static class Shark {
        int r;
        int c;
        int size;
        int countEattingFish;

        public Shark(int r, int c, int size, int countEattingFish) {
            this.r = r;
            this.c = c;
            this.size = size;
            this.countEattingFish = countEattingFish;
        }
    }

}

 

84ms의 정답코드 (참고한 코드)

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

public class Main {
    static int N;
    static int[][] map;
    static boolean[][] visited;
    static Queue<Point> queue;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        queue = new ArrayDeque<>();
        visited = new boolean[N][N];

        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) {
                    queue.add(new Point(i, j));  // 아기상어 초기 위치, 크기:2
                    map[i][j] = 0;  // 아기 상어 위치 빈칸으로 바꿔주기
                    visited[i][j] = true;
                }
            }
        }
        bfs();
        System.out.println(result);
    }
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int result;

    public static void bfs(){
        int sharkSize = 2;  // 상어 크기
        int feedCnt = 0;    // 먹이 먹은 개수
        result = 0;     // 결과

        PriorityQueue<Point> pq = new PriorityQueue<>();
        int round = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int s = 0; s < size; s++) {
                Point shark = queue.poll();

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

                    int nexti = shark.i + dx[d];
                    int nextj = shark.j + dy[d];

                    if (nexti >= 0 && nexti < N && nextj >= 0 && nextj < N && !visited[nexti][nextj]) {
                        // map 범위 안일 때
                        if ( map[nexti][nextj] != 0 && map[nexti][nextj] < sharkSize) {
                            pq.add(new Point(nexti, nextj));
                        }
                        if (map[nexti][nextj] <= sharkSize) {
                            queue.add(new Point(nexti, nextj));
                            visited[nexti][nextj] = true;
                        }
                    }
                }
            }
            round++;
            // pq가 비어있지않다면?
            if (!pq.isEmpty()) {
//                System.out.println(pq);
//                System.out.println("round : " + round);
                Point feed = pq.poll();
                feedCnt++;
                map[feed.i][feed.j] = 0; // 먹이 먹었으니까 빈칸으로 만들어주고

                if (feedCnt == sharkSize) {
                    sharkSize++;
                    feedCnt = 0;
                }
                result = round;
//                System.out.println("result : " + result);
                pq.clear();
                queue.clear();
                visited = new boolean[N][N];
                queue.add(new Point(feed.i, feed.j));
                visited[feed.i][feed.j] = true;
            }
        }
    }
    public static class Point implements Comparable<Point> {
        int i, j;

        public Point(int i, int j) {
            this.i = i;
            this.j = j;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "i=" + i +
                    ", j=" + j +
                    '}';
        }

        // 가장 위에 물고기 선택 but 그런 물고기 많다면 가장 왼쪽 물고기 냠
        @Override
        public int compareTo(Point o) {
            if (this.i == o.i) {
                return this.j - o.j;
            }
            else return this.i - o.i;
        }
    }
}