[알고리즘 문제 풀이] 백준 16236 아기 상어

 

 

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

 

 

 

 

 

import java.util.StringTokenizer;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;

import java.util.ArrayList;
import java.util.List;

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


public class Main {

    static int N;
    static int[][] arr;

    static int sharkSize;

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

    static int sharkX,sharkY;

    static int time;
    static boolean[][] visited;

    static Queue<Node> q;
    static int eatCount;

    public static class Node{
        int y;
        int x;

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

    public static class Fish{
        int y;
        int x;
        int distance;

        public Fish(int y,int x, int distance){
            this.y=y;
            this.x=x;
            this.distance = distance;
        }

    }

    static Fish fish = new Fish(-1,-1,Integer.MAX_VALUE);


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

        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));


        StringTokenizer st= new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        arr = new int[N][N];

        sharkSize = 2;
        time =0;

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());

                if(arr[i][j]==9){
                    sharkY=i;
                    sharkX=j;
                    arr[i][j]=0; // 상어 초기 위치를 빈칸으로 설정
                }
            }
        }
        // arr[sharkY][sharkX]

        while (true) {
            checkFish();
            if (fish.y == -1) {
                System.out.println(time);
                break;
            }
            moveToFish();
        }

    }


    static void checkFish(){
        Queue<Node> q= new LinkedList<>();
        visited = new boolean[N][N];

        fish.distance = Integer.MAX_VALUE;
        fish.y=-1;
        fish.x=-1;

        q.offer(new Node(sharkY,sharkX,0));
        visited[sharkY][sharkX]=true;

        while(!q.isEmpty()){
            Node node = q.poll();

            for(int i=0;i<4;i++){
                int nextY = node.y +dy[i];
                int nextX = node.x +dx[i];

                if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N || visited[nextY][nextX]) continue;

                // 이미 방문 했다면 통행 필요 X
                if(visited[nextY][nextX]) continue;

                // 크기가 더 크면 통행 불가
                if(arr[nextY][nextX] > sharkSize ) continue;
                
                visited[nextY][nextX]=true;

                if (arr[nextY][nextX] <= sharkSize){
                    int distance = node.time + 1;

                    q.offer(new Node(nextY,nextX,distance));

                    if(arr[nextY][nextX] < sharkSize && arr[nextY][nextX] >0){
                        if(distance < fish.distance ||
                                (distance==fish.distance && (nextY < fish.y || nextY==fish.y && nextX<fish.x))){
                            fish.y= nextY;
                            fish.x=nextX;
                            fish.distance = distance;
                        }

                    }
                }


            }
        }
    }

    static void moveToFish(){
        time +=fish.distance;
        eatCount++;
        if (eatCount == sharkSize) {
            sharkSize++;
            eatCount = 0;
        }
        arr[fish.y][fish.x]=0;
        sharkY=fish.y;
        sharkX=fish.x;
    }


}