백준 (BOJ) 16236 아기 상어 java

* 풀이가 아니니 문제 풀이하시는 데에 참고하지 않길 당부드립니다.

 

풀다가 테스트케이스에서 여러 번 막힌 덕분에 약간의 분노를 느껴 복습을 위해 남기는 포스트이다.

항상 구현/시뮬레이션 문제 풀면 조건 확실히 숙지하고 가자.

 

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고,

나머지 칸은 모두 지나갈 수 있다.

따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.
아기 상어는 자신의 크기와 같은 수(2렙이면 2마리, 3렙이면 3마리)의 물고기를 먹을 때 마다 크기가 1 증가한다.

 

 

테케 3번 진행 이미지)

위의 이미지는 잘못되었다. 처음 1을 섭취한 후 3을 지나 저렇게 갈 수 없다.

해당 시점에 아기 상어의 크기는 2이기 때문이다. 자신 보다 큰 3을 지날 수 없다.

처음 조건을 잘못 이해해서 저기서 꽤 고생했다. 반면교사하자.

 

 

 

1. q만 쓰면 될 것 같았는데 결국 pq도 썼다.

 

먼저 q로 탐색 범위를 훑고,

 

다음 pq는 해당 phase에서 먹을 수 있는 물고기들이 나왔을 때 다음의 우선 순위

 

① 최단 거리

 

② 보다 높은 위치

 

③ 보다 왼쪽 위치

 

를 만족시켜서, 먹을 수 있는 물고기의 위치를 넣으면 알아서 정렬시켜준다.

 

그리고 조건을 만족시키는 도착 지점의 위치를 함수의 끝에서 뱉어준다(poll).

 

물론 다 q로 다 훑었는데도 찾지 못했다면, boolean check가 false로 나타나 끝에서 잘못된 place를 뱉는다.

(이 부분은 bfs 메서드의 return 타입을 boolean으로 맞춰서 더 최적화할 수 있을 거 같다.)

 

잘못된 place를 받은 main에서 판단하여, 엄마 상어를 부를 것인지를 정한다. (boolean flag가 체크 후 루프 종료)

 

그리고 q, pq와 visited는 매번 시작지점으로부터 진행될 때마다 bfs에서 새로 할당된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

// ***** 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고,
// 나머지 칸은 모두 지나갈 수 있다.
// 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.
// 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
// ** 아기 상어는 자신의 크기와 같은 수(2렙이면 2마리, 3렙이면 3마리)의 물고기를 먹을 때 마다 크기가 1 증가한다.

class place implements Comparable<place>{
    int x, y, count;
    place(int x, int y, int count){
        this.x = x;
        this.y = y;
        this.count = count;
    }

    @Override
    public int compareTo(place p){
        // 우선 순위 1: 이동 거리
        if(this.count > p.count){ // 새로 들어오는 p가 짧다면, 1 return
            return 1;
        }else{
            // 우선 순위 2: 높이
            if(this.y > p.y) return 1; // 앞에 위치
            else if(this.y == p.y){ // 높이가 같다면, 우선 순위 3: 왼쪽
                if(this.x > p.x) return 1;
                else return -1;
            }
            else return -1; // 뒤에 위치
        }
    }
}

public class Main {
    static int[][] map;
    static int N;
    static int[] dx = {0,-1,0,1};
    static int[] dy = {-1,0,1,0};
    static boolean[][] visited;
    static int level;  // 현재 아기 상어의 크기(level)
    static int needed; // 다음 레벨로 가기 위해 요구되는 상어 수
    static PriorityQueue<place> pq; // 해당 phase 에서 "최단 거리, 더 높은, 왼쪽"을 기준으로 정렬된 pq
    static Queue<place> q;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        int x = 0, y = 0; // the current place of a baby shark.

        StringTokenizer st;
        for(int i=0; i<N; ++i){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; ++j){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 9){
                    y = i;
                    x = j;
                    map[i][j] = 0;
                }
            }
        }

        boolean flag = true;
        int count = 0; // 총 움직인 시간, 초기 값 == 0
        level = 2; // 시작 크기
        needed = level; // 필요한 먹이 수(시작은 level 동일)

//      System.out.println("시작 위치= " + x + " " + y);
        while (flag){
            place p = bfs(x, y, count);
            if(p.x == -1 && p.y == -1){
                flag = false;
            }else{
                x = p.x;
                y = p.y;
                count = p.count;
                //*** '먹음' 처리: return 될 때 실제 방문하는 place 를 받을 수 있다.
                map[y][x] = 0;
//              System.out.println("위치= " + x + " " + y + ", 이동거리= " + count + ", level= " + level);
            }
        }

        System.out.print(count);
    }

    public static place bfs(int x, int y, int count){
        // 새로 선언해줘야 할 3가지 것들.
        visited = new boolean[N][N];
        q = new LinkedList<>();
        pq = new PriorityQueue<>();

        q.add(new place(x, y, count));
        visited[y][x] = true;
        boolean check = false; // 먹을 거 있나 체크

        while (!q.isEmpty()){
            place p = q.poll();
            int px = p.x;
            int py = p.y;
            int pCount = p.count+1; // 미리 한 칸 이동할 거 생각해서 더해놓기

            for(int i=0; i<4; ++i){
                int nx = px + dx[i];
                int ny = py + dy[i];
                if(nx >= 0 && nx < N && ny >= 0 && ny < N){
                    if(!visited[ny][nx] && map[ny][nx] <= level){
                        // 지나갈 수 있는 곳이므로, 일단 방문체크
                        visited[ny][nx] = true;

                        // 빈 공간이 아니고, 현재 아기상어 레벨 보다 낮으면 '먹음'
                        if(map[ny][nx] < level && 0 < map[ny][nx]){
                            check = true; //** '먹을 것 있나' 체크

                            // 일단 후보군 중 하나는 넣고보자.
                            pq.add(new place(nx, ny, pCount));
                        }else{ // 먹이가 아닌 곳을 지난다면,
                            if(!check) {
                                q.add(new place(nx, ny, pCount));
                            }
                        }
                    }
                }
            }
        }

        if(check){
            // 먹을 것 찾았으니까, 요구되는 '먹이' 감소
            --needed;

            // 필요한 만큼 먹어치웠다면: level up, needed 갱신
            if(needed == 0){
                ++level;
                needed = level;
            }// else 생략: 먹긴 먹었는데 아직 덜 먹었다면, pass
            return pq.poll();
        }
        else{
            return new place(-1, -1, -1);
        }
    }
}