백준 16236 - 아기상어

시뮬레이션 + BFS

BFS를 여러번 실행하는 방법이 필요

참고 : na982 블로그

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int N;
    static int[][] map;
    static boolean[][] visited;
    static int sharkEat, sharkSize;
    static Shark shark;
    static int[] dy = { 0, 0, -1, 1};
    static int[] dx = {-1 ,1, 0 , 0};
    static class Shark{

        int y;
        int x;
        int time;

        Shark(int y, int x, int time){

            this.y = y;
            this.x = x;
            this.time = time;

        }
    }


    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        map = new int[N][N];
        for(int y=0; y<N; y++){
            for(int x=0; x<N; x++){
                map[y][x] = sc.nextInt();
                if(map[y][x] == 9){
                    map[y][x] = 0;
                    shark = new Shark(y, x, 0);
                    sharkEat = 0;
                    sharkSize = 2;
                }
            }
        }

        BFS();

        System.out.println(shark.time);

    }

    private static void BFS() {

        boolean isUpdate = true;

        while(isUpdate){

            isUpdate = false;
            visited = new boolean[N][N];
            Queue<Shark> queue = new LinkedList<>();

            visited[shark.y][shark.x] = true;
            queue.add(shark);


            Shark sharkFeed = new Shark(20,0, -1);

            while(!queue.isEmpty()){

                Shark cur = queue.poll();

                if(sharkFeed.time != -1 && sharkFeed.time < cur.time){
                    break;
                }

                if(map[cur.y][cur.x] != 0 && map[cur.y][cur.x] < sharkSize){
                    isUpdate = true;

                    if(sharkFeed.y > cur.y  || (sharkFeed.y == cur.y && sharkFeed.x > cur.x)){ // 가장 위쪽에 있는 물고기를 먹고 만약 여러 마리라면 가장 왼쪽에 있는 물고기를 먹음
                        sharkFeed = cur;
                    }
                }

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

                    Shark nextShark = new Shark(cur.y+dy[i],cur.x+dx[i], cur.time+1);

                    if(nextShark.y < 0 || nextShark.y >= N || nextShark.x <0 || nextShark.x >= N)continue;
                    if(visited[nextShark.y][nextShark.x] == false && map[nextShark.y][nextShark.x] <= sharkSize){
                        queue.add(nextShark);
                        visited[nextShark.y][nextShark.x] = true;
                    }

                }


            }

            if(isUpdate){
                shark = sharkFeed;
                sharkEat++;
                if(sharkSize == sharkEat){
                    sharkSize++;
                    sharkEat=0;
                }
                map[shark.y][shark.x] = 0;
            }

        }

    }
}