백준 16236 아기상어 - Java

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

 

풀이

문제의 이 조건 때문에 조금 까다로웠다.

"먹을 수 있는 생선이 한마리면 그것을 먹고 

두 마리 이상이면 가장 가까운 거리의 생선을 먹는다. 또한 가장 가까운 거리의 생선이 여러마리면 가장 위에 생선을 먹고

가장 위에 생선역시 여러마리면 가장 좌측의 생선을 먹는다"

이 부분에서 해맸지만 레벨탐색으로 레벨마다 체크한다면 거리는 따질 필요가 없으니 좌표만을 비교해 구하면 된다는 것을 깨달았다.!!

 

 

나의 풀이 순서는 다음과 같다.

1. 입력받은 생선이 1마리 이상이면 실행 아니면 0 출력
2. 상어가 갈 수 있는 곳을 탐색한다. (상어크기 이하면 갈 수 있음)
    2-1. 상어크기와 생선크기다 똑같다. 이동만 수행.
    2-2. 상어크기보다 생선이 작아서 먹을 수 있으니 fish라는 우선순위 큐에 넣는다.
3. 레벨마다 fish 우선순위 큐를 기준으로 먹을 수 있는 상어가 있는지 체크한다.
    3-1. fish 우선순위 큐가 비어있지 않으면 먹을 수 있으니 큐에서 꺼낸다음 갱신(상어 크기와 위치, 걸린 시간 갱신)
    처리 후 종료한다.  (이러면 BFS를 끝까지 돌지 않아도 됨)

주의:

처음 이 문제를 풀었을때 메모리 초과로 실패했다. 그 이유는 상어가 물고기를 탐색하기 위해 상어와 물고기의 거리를 담아놓는 

int [][] dis를 사용했는데 상어는 -1 , 나머지는 10000 으로 초기화해서 메모리가 커진것이다.

때문에 bollean형의 visited 2차원 배열로 바꿔 해결할 수 있었다.

 

전체코드

import java.util.*;
class Main {
    static int sec; // 총 걸린시간
    static int eatCnt, sharkSize; // 먹은 생선 수와 상어 사이즈
    static int n,y,x;
    static int [][] arr;
    static int[] dy = {-1,0,1,0};
    static int[] dx = {0,1,0,-1};
    static boolean gotoEat(){
        // 먹을 수 있는 상어를 넣는 우선순위 큐
        PriorityQueue<int[]>fish = new PriorityQueue<>
                ((a,b) -> ( a[1]==b[1] ? a[2]-b[2] :a[1]-b[1] ) );
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{ y, x}); // 상어
        boolean [][]  visited = new boolean[n][n];
        visited[y][x] = true;
        /**
         * BFS
         */
        int L = 0;
        while (!q.isEmpty()){
            int len = q.size();
            for(int i=0;i<len;i++){
                int[] po = q.poll();
                for(int j=0; j<4; j++){
                    int ny = po[0] + dy[j];
                    int nx = po[1] + dx[j];
                    if( ny<0 || ny>=n || nx<0 || nx>=n ) continue;
                    if( visited[ny][nx] || arr[ny][nx] > sharkSize) continue;
                    // 이동은 가능
                    q.offer(new int[]{ny,nx} );
                    visited[ny][nx] = true;
                    // 먹는것도 가능
                    if(arr[ny][nx]!=0 && arr[ny][nx]< sharkSize){
                        fish.offer(new int[]{ L+1,ny,nx} ); // 먹을 수 있는 생선의 [ 거리 + 좌표 ]
                    }
                }
            }
            /**
             * 레벨마다 먹을 수 있는 생선 체크 : 레벨마다 체크하면 그냥 거리체크안하고 좌표값만으로 따질 수 있음 + 한마리먹으면 바로 종료
             * fishCheck(fish)가 참이면 물고기 먹은걸로 처리되고 갱신(상어 크기와 위치, 걸린 시간 갱신) 후 종료
             */
            if(fishCheck(fish)){ //
                return true;
            }
            L++;
        }
        return false;
    }
    private static boolean fishCheck(PriorityQueue<int[]> fish) {
        if(fish.isEmpty()) return false;
        else{
            int [] p = fish.poll();
            int dis = p[0];
            int moveY = p[1];
            int moveX = p[2];
            // 먹은곳으로 상어 위치 변경
            y= moveY;
            x= moveX;
            // 물고기 먹음
            eatCnt++;
            // 먹은 물고기 갱신(크기 커질수도)
            if(sharkSize==eatCnt){
                sharkSize++;
                eatCnt=0;
            }
            // 먹은 물고기는 제거
            arr[moveY][moveX] = 0;
            // 먹으러 가는데 걸린시간 갱신
            sec+= dis;
            return true;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //
        int fishCnt=0;
        sharkSize=2; // 상어 사이즈
        eatCnt=0; // 먹은 물고기
        sec = 0; // 시간
        // 아기상어 시작 좌표
        y=x=0;
        n = sc.nextInt();
        arr = new int[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                int m = sc.nextInt();
                if( m<9 && m>0){
                    fishCnt++;
                    arr[i][j] = m;
                }
                //아기상어
                else if(m==9){
                    y=i;
                    x=j;
                }
            }
        }
        /**
         * 입력에 생선이 있으면 먹을 수 있을때까지 먹고 종료시간 출력
         */
        if(fishCnt>0){
            //먹을 수 있을때까지 먹음
            while (gotoEat()){}
        }
        // output
        System.out.println(sec);
    }
}