[백준 16236, Java] 아기상어

문제

 

풀이

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Shark{
    int x;
    int y;
    int size;
    int eatCount;
    static int totalEatCount = 0;
    static int totalMoveCount =0;

    Shark(int x, int y, int size, int eatCount){
        this.x = x;
        this.y = y;
        this.size = size;
        this.eatCount = eatCount;
    }
}
class Point{
    int x;
    int y;
    int distance;

    Point(int x, int y, int distance){
        this.x = x;
        this.y = y;
        this.distance = distance;
    }
}
public class Main {
    public static int N;
    public static int[][] map;
    public static boolean[][] visited;
    public static Shark shark;
    public static Point fish;
    public static Queue<Point> queue;
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, 1, 0, -1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for(int r = 0; r<N; r++){
            st = new StringTokenizer(br.readLine()," ");
            for(int c =0 ;c<N; c++){
                int sizeOfFish = Integer.parseInt(st.nextToken());
                if(sizeOfFish==9){
                    shark = new Shark(r, c ,2, 0);
                    map[r][c] = 0;
                }
                else{
                    map[r][c] = sizeOfFish;
                }
            }
        }

        bfs();

        bw.write(String.valueOf(Shark.totalMoveCount));
        bw.flush();
        br.close();
        bw.close();


    }

    public static void bfs(){

        while (true) {

            // 현재 상어의 위치기준
            queue = new LinkedList<>();
            queue.add(new Point(shark.x, shark.y, 0));
            int eatCount = 0;

            //탐색 (현재 상어의 위치에서 먹을 수 있는 물고기가 있는지 확인
            visited = new boolean[N][N];
            visited[shark.x][shark.y] = true;
            fish = new Point(N, N, N*N);
            while(!queue.isEmpty()){
                Point currentShark = queue.poll();

                if(currentShark.distance> fish.distance){
                    break;
                }
                if(map[currentShark.x][currentShark.y]!=0 && map[currentShark.x][currentShark.y]< shark.size){
                    Point candidateFish = new Point(currentShark.x, currentShark.y, currentShark.distance);
                    eatCount = 1;

                    if(candidateFish.x< fish.x){
                        fish = candidateFish;
                    }
                    else if(candidateFish.x == fish.x){
                        if(candidateFish.y< fish.y){
                            fish = candidateFish;
                        }
                    }
                }
                else{
                    //현재위치에 먹을 수 있는 물고기가 없다.
                    for(int d = 0; d<4; d++){
                        int nx = currentShark.x + dx[d];
                        int ny = currentShark.y + dy[d];
                        int nd = currentShark.distance + 1;
                        if(nx>=0 && ny>=0 && nx<N && ny<N){
                            if(map[nx][ny]<= shark.size && !visited[nx][ny]){
                                visited[nx][ny] = true;
                                queue.add(new Point(nx,ny,nd));
                            }
                        }
                    }
                }

            }
            //탐색 종료조건 ->더 이상 이동할 수 있는 곳이 없거나 물고기를 먹었거나
            if(eatCount ==0){
                break;
            }
            else{
                map[fish.x][fish.y] = 0;

                shark.x = fish.x;
                shark.y = fish.y;
                ++shark.eatCount;
                Shark.totalMoveCount += fish.distance;

                if(shark.eatCount== shark.size){
                    ++shark.size;
                    shark.eatCount = 0;
                }
                Shark.totalEatCount++;

            }
        }



    }
}