[BFS] 아기상어 (두번째)

백준 16236 아기상어 (삼성 SW 역량테스트 기출)

https://www.acmicpc.net/problem/16236

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

public class Main {

    static int N;
    static int[][] map;
    static int[][] visited;

    static int n;
    static int m;

    static int size=2;
    static int stomach=0;
    static int count=0;

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

    static int fishCount=0;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        map = new int[N+1][N+1];
        visited = new int[N+1][N+1];

        //맵 입력받기
        for(int i=1; i<=N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++){
                int a = Integer.parseInt(st.nextToken());
                if(a==9){
                    n=i; m=j;
                }else if(0<a && a<=6){
                    fishCount++;
                    map[i][j] = a;
                }
            }
        }

        loop();
        System.out.println(count);
    }

    static void loop(){

        boolean foodExist = true;
        while (foodExist && 0<fishCount){
            foodExist = bfs();
        }
    }


    static boolean bfs(){

        Queue<Position> q= new LinkedList<>();
        q.add(new Position(n,m));
        visited = new int[N+1][N+1];

        //걸려든 물고기들
        PriorityQueue<Position> pq = new PriorityQueue<>();

        int moving=0;
        while (!q.isEmpty()){

            moving++;

            //한껍질씩 체크
            int qSize = q.size();
            for(int i=0; i<qSize; i++){
                Position now = q.poll();

                //4방향
                for(int j=0; j<4; j++){
                    int nN = now.n + dn[j];
                    int nM = now.m + dm[j];

                    if(isIn(nN, nM) && isBigger(nN, nM)==false && visited[nN][nM]==0){
                        visited[nN][nM] = 1;
                        q.add(new Position(nN, nM));

                        if(isEatable(nN,nM)){
                            pq.add( new Position(nN, nM));
                        }
                    }
                }
            }//껍질 끝

            if(!pq.isEmpty()){
                count += moving;
                eat(pq.poll());
                return true;
            }

        }
        return false; //먹을 수 있는 게 없다
    }


    static void eat(Position fish){

        map[fish.n][fish.m] = 0;
        fishCount--;
        n = fish.n;
        m = fish.m;

        stomach++;
        if(stomach==size){
            size++;
            stomach=0;
        }
    }

    //못가는지 확인
    static boolean isBigger(int n, int m){
        if(size < map[n][m]) return true;
        return false;
    }

    //먹을 수 있는지 확인
    static boolean isEatable(int n, int m){
        if(0<map[n][m] && map[n][m] < size) return true;
        return false;
    }


    static boolean isIn(int n, int m){
        if(n<1 || N<n || m<1 || N<m) return false;
        return true;
    }


    static class Position implements Comparable<Position>{
        int n;
        int m;

        Position(int n, int m){
            this.n = n;
            this.m = m;
        }

        @Override
        public int compareTo(Position o) {
            if(this.n < o.n) return -1;
            else if(this.n==o.n){
                if(this.m < o.m) return -1;
                else return 1;
            }
            else return 1;
        }
    }
}