백준 16236 - 아기 상어 (Java)

장준혁·2024년 4월 4일

Java coding test

coding-test

목록 보기

10/21

🔍 문제

💻 제출

📌 입력

📌 출력

🤔 생각

문제에 생각보다 고려 할 점이 많다.

상어는 본인보다 작은 물고기 만 먹을 수 있고 자신의 level보다 큰 물고기 영역에는 접근 할 수 없다.
이동 할 때는 빈 공간 과 자신과 level이 동일 하거나 낮은 영역으로 이동 해야 한다.
또한 동일한 거리에 물고기가 존재 한다면 위쪽 -> 왼쪽 -> 오른쪽 -> 아래쪽 으로 우선순위를 가진다.

위 우선순위가 문제를 푸는 가장 골칫거리 이자 해결할 수 있는 열쇠 라고 생각 했다.

물고기의 우선순위가 존재 하기 때문에 좌표 값을 확인 하면서 진행 해야하는데 매번 값을 꺼내서 직접 확인 하는 것 보다 우선순위 큐를 사용 하여 자동으로 정렬이 되도록 했다.

📝 코드


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

public class Main {
    static int N;
    static int[][] map;
    static long fish = 0;
    static Shark start;
    static int[] dx = {-1, 0, 0, 1}; //북 서 동 남
    static int[] dy = {0, -1, 1, 0}; //북 서 동 남

    static class Shark {
        int x;
        int y;
        int level;
        int levelCnt;
        long d;

        public Shark(int x, int y, int level, int levelCnt, long d) {
            this.x = x;
            this.y = y;
            this.level = level;
            this.levelCnt = levelCnt;
            this.d = d;
        }
    }

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

        N = Integer.parseInt(br.readLine());

        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 9) {
                    start = new Shark(i, j, 2,2,0);
                } else if (map[i][j] != 9 && map[i][j] != 0) {
                    fish++;
                }
            }
        }

        while (fish != 0) { //모든 물고기가 없어질 때 까지

            Shark S = bfs(start);

            if(S == null){
                break;
            }
            else{
                start = S;
            }
        }

        bw.write(start.d + "\n");
        bw.flush();
        bw.close();
    }

    static Shark bfs(Shark start) {
        PriorityQueue<Shark> q = new PriorityQueue<>((a, b) ->
                a.d != b.d ?
                        Long.compare(a.d,b.d) :  // distance 가 다르다면 오름차순 반환 (true)
                        (a.x != b.x ? //distance 가 같다면 x좌표 비교
                                Integer.compare(a.x,b.x) : //x좌표 다르다면 x좌표 오름차순 반환
                                Integer.compare(a.y,b.y) //x 좌표가 같다면 y좌표 오름차순 반환
                        )
        );

        q.offer(start);
        map[start.x][start.y] = 0; //처음 시작 위치는 빈공간으로 변경

        boolean[][] visited = new boolean[N][N];
        visited[start.x][start.y] = true;

        while (!q.isEmpty()) {
            Shark nowS = q.poll();

            if (map[nowS.x][nowS.y] != 0  && map[nowS.x][nowS.y] < nowS.level){
                //상어보다 level 이 낮은 물고기 공간

                fish--; //전체 물고기 감소
                map[nowS.x][nowS.y] = 0; //빈 공간으로 취급

                if (nowS.levelCnt - 1 == 0){ //업그레이드에 필요한 물고기 수 1 감소
                    //업그레이드에 필요한 물고기 개수를 다 채웠다면

                    //현재 level 증가
                    //level 증가한 만큼 cnt 도 변화
                    return new Shark(nowS.x,nowS.y, nowS.level + 1, nowS.level + 1 , nowS.d);
                }
                else{
                    return new Shark(nowS.x,nowS.y, nowS.level, nowS.levelCnt - 1 , nowS.d);
                    //물고기 먹은 개수만 줄여준다
                }
            }
            
            //물고기 영역이 아니라면
            for (int i=0; i<4; i++){
                int nx = nowS.x + dx[i];
                int ny = nowS.y + dy[i];
                
                if (0<=nx && nx<N && 0<=ny && ny<N){
                    if (visited[nx][ny] == false && map[nx][ny] <= nowS.level){
                        //방문하지 않았던 영역이어야 하고
                        //상어의 level 보다 낮거나 같은 영역으로 이동 가능

                        q.offer(new Shark(nx,ny, nowS.level, nowS.levelCnt, nowS.d+1));
                        visited[nx][ny] = true;
                    }
                }
            }
            
        }

        return null;
    }

}

📗 정리


PriorityQueue<Shark> q = new PriorityQueue<>((a, b) ->
                a.d != b.d ?
                        Long.compare(a.d,b.d) :  // distance 가 다르다면 오름차순 반환 (true)
                        (a.x != b.x ? //distance 가 같다면 x좌표 비교
                                Integer.compare(a.x,b.x) : //x좌표 다르다면 x좌표 오름차순 반환
                                Integer.compare(a.y,b.y) //x 좌표가 같다면 y좌표 오름차순 반환
                        )
        );