문제

풀이

• 물고기 우선 순위 주의하기

1. bfs 진행해서 먹을 수 있는 물고기가 있으면 후보 리스트에 추가
2. 물고기 후보 리스트 정렬
3. 물고기 먹으면 초기화 후 다시 bfs 진행
4. 먹을 수 있는 물고기가 없으면 종료

   ---

코드

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

public class Main {
    static int y, x;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int[][] map = new int[n][n];
        int size = 2, eat = 0, time = 0, min = 9;
        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) {
                    y = i;
                    x = j;
                    map[i][j] = 0;
                } else if (map[i][j] != 0) {
                    min = Math.min(map[i][j], min);
                }
            }
        }
        if (min > size) {
            System.out.println(0);
            return;
        }
        int[][] d = new int[][] { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(y, x, 0));
        int[][] v = new int[n][n];
        v[y][x] = 1;
        ArrayList<Pos> fishes=new ArrayList<>();
        while(true){
            while (!q.isEmpty()) {
                Pos now = q.poll();

                for (int i = 0; i < 4; i++) {
                    int dy = now.y + d[i][0];
                    int dx = now.x + d[i][1];
                    if (dy < 0 || dx < 0 || dy >= n || dx >= n)
                        continue;
                    if (map[dy][dx] <= size && v[dy][dx] == 0) {
                        q.add(new Pos(dy, dx, now.time + 1));
                        v[dy][dx] = 1;
                        if (map[dy][dx] != 0 && map[dy][dx] < size) {
                            fishes.add(new Pos(dy,dx, now.time+1));
                        }
                    }
                }
            }
            if(!fishes.isEmpty()){
                Collections.sort(fishes);
                eat++;
                int dy=fishes.get(0).y;
                int dx=fishes.get(0).x;
                map[dy][dx] = 0;
                if (eat == size) {
                    size++;
                    eat = 0;
                }
                time = fishes.get(0).time;
                q.clear();
                q.add(new Pos(dy, dx, fishes.get(0).time));
                v = new int[n][n];
                v[dy][dx] = 1;
                fishes.clear();
            }
            else break;
        }

        System.out.println(time);
    }

    static class Pos implements Comparable<Pos>{
        int y, x, time;

        public Pos(int y, int x, int time) {
            this.y = y;
            this.x = x;
            this.time = time;
        }

        @Override
        public int compareTo(Pos o) {
            if(this.time!=o.time)return this.time-o.time;
            else{
                if(this.y!=o.y)return this.y-o.y;
                else return this.x-o.x;
            }
        }
    }
}

#bfs