[PS] BOJ16236 아기상어 ( 구현 ) with JAVA

 

 

16236번: 아기 상어

 

 

◎ 문제풀이

 

• 문제요약 : 2차원 배열에서 아기상어가 상하좌우로 이동하여 가장 가까운(가장 우선순위가 높은) 먹이를 먹을 때, 먹이를 더이상 먹지 못하고 엄마상어를 부를 때까지 걸리는 시간을 구하라.
• 문제풀이 : 
  • 상하좌우로 이동하며 가장 가까운 먹이를 찾는다는 점에서 최단거리를 구하는 BFS를 떠올렸다.
  • BFS까지는 떠올렸으나 일반적인 BFS 코드로는 먹이를 먹는 우선순위를 적용하기 힘들었다.
  • 일반큐가 아닌 우선순위큐를 사용하여 조건에 맞는 가장 가까운 먹이를 찾는다.
  • 먹이를 먹는 로직을 처리 후 다시 그 지점부터 먹이찾기를 반복한다. ( while )
• 고려하지 못한 점
  • BFS에서 우선순위큐를 사용하여 로직을 모르고 있었다.

 

◎ 코드

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


//BOJ16236 아기 상어
public class Main {

    static int n;
    static int[][] matrix;
    static int startX,startY;

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


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

        n = Integer.parseInt(br.readLine());
        matrix = new int[n][n];

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

                if(value == 9){
                    startX = j;
                    startY = i;
                }
            }
        }

        SharkMove currSharkMove = new SharkMove(startX,startY,0);

        int sharkSize = 2;
        int eatCount = 0;
        int ans = 0;

        while(true){
            PriorityQueue<SharkMove> queue = new PriorityQueue<>();
            boolean[][] visited = new boolean[n][n];
            boolean isEat = false;
            queue.add(currSharkMove);
            visited[currSharkMove.y][currSharkMove.x] = true;
            matrix[currSharkMove.y][currSharkMove.x]=0;


            while(!queue.isEmpty()){
                SharkMove sharkMove = queue.poll();


                if(matrix[sharkMove.y][sharkMove.x] != 0 && matrix[sharkMove.y][sharkMove.x] < sharkSize) {
                    ans += sharkMove.move;
                    currSharkMove = new SharkMove(sharkMove.x, sharkMove.y,0);
                    eatCount += 1;
                    if(eatCount == sharkSize) {
                        sharkSize += 1;
                        eatCount = 0;
                    }
                    isEat = true;
                    break;
                }

                for(int i=0;i<4;i++){
                    int nx = sharkMove.x + dx[i];
                    int ny = sharkMove.y + dy[i];

                    if(isValid(nx,ny)&&!visited[ny][nx]) {
                        if(matrix[ny][nx] <= sharkSize){
                            visited[ny][nx] = true;
                            queue.add(new SharkMove(nx,ny,sharkMove.move+1));
                        }
                    }
                }
            }

            if(!isEat) break;
        }


        System.out.println(ans);

    }

    public static boolean isValid(int x, int y){
        return ( x<n&&y<n&&x>=0&&y>=0 )? true : false;
    }


    public static class SharkMove implements Comparable<SharkMove>{
        int x;
        int y;
        int move;

        public SharkMove(int x, int y, int move){
            this.x = x;
            this.y = y;
            this.move = move;
        }

        @Override
        public int compareTo(SharkMove s){
            if(this.move == s.move){
                if(this.y == s.y) return this.x - s.x;
                else return this.y - s.y;
            }else{
                return this.move - s.move;
            }

        }
    }


}