[백준] 16236번: 아기 상어 - JAVA

🔗 문제 링크

BOJ 16236번: 아기 상어

16236번: 아기 상어

 

📝 풀이 과정

문제의 규칙을 먼저 정리해보았다.

1. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다.
2. 자신의 물고기보다 작은 물고기만 먹을 수 있다.
3. 더 이상 먹을 물고기가 존재하지 않는다면 도움을 요청한다
4. 먹을 수 있는 물고기가 많다면 거리가 가깝거나, 가장 위에 있거나, 가장 왼쪽에 있는 물고기 순으로 먹는다.
5. 물고기가 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1씩 증가한다.

문제의 핵심은 4번이다. 이 규칙만 제거하면 일반적인 BFS와 유사하지만 해당 조건으로 인해 거리뿐이 아닌 물고기의 위치까지 함께 고려해 주어야 하기 때문이다.

 

 

Icons made by  플랫 아이콘  from  www.flaticon.com

일반적인 BFS로 구현할 경우 생길 수 있는 문제에 대해 알아보자. 상어가 위쪽, 왼쪽에 있을수록 먼저 탐색해야 하기 때문에 BFS의 순서를 (상, 좌, 우, 하) 순으로 탐색한다고 가정해보았다.

 

(1, 1)에 size가 3인 아기 상어가 있고, 위쪽에는 size가 4인 물고기가 있어 갈 수 없기 때문에 왼쪽인 (1, 0), 오른쪽인 (1, 2) 순으로 Queue에 들어가게 된다. 순서대로 poll을 진행하면 먼저 들어간 순서대로 나오기 때문에 왼쪽 좌표가 먼저 나오게 되고 4방향 탐색을 통해 (2, 0)에 존재하는 먹이를 먼저 먹게 된다.

 

하지만, 규칙에 따르면 (0, 2)에 존재하는 먹이가 더 위쪽에 있기 때문에 먼저 먹어야 하므로 잘못된 결과가 나왔다는 것을 알 수 있다. 따라서, 일반적인 BFS가 아닌 우선순위를 활용한 BFS가 필요하다는 것을 알 수 있다.

 

 

PriorityQueue<int[]> que = new PriorityQueue<>((o1, o2) ->
    o1[2] != o2[2] ? Integer.compare(o1[2], o2[2]) : (o1[0] != o2[0] ? Integer.compare(o1[0], o2[0]) : Integer.compare(o1[1], o2[1]))
);

우선순위 큐는 생성하며 Comparator를 활용해 우선순위를 설정할 수 있는데 int[]배열(순서대로 {y좌표, x좌표, 움직인 거리})을 사용하여 Queue에 넣어주었다. 거리가 다르다면 거리 순으로 오름차순, y축 좌표가 다르다면 y축 좌표로 오름차순 모두 같다면 x축 좌표로 오름차순 정렬을 해주었다.

 

먹이를 먹을 때마다 상어의 위치가 갱신되므로 while(true)를 통해 반복을 해주었고, boolean ck변수를 활용해 상어가 갈 수 있는 모든 위치를 돌았을 때 물고기를 먹었는지 먹지 않았는지 판별한다. 만약 물고기를 먹지 않았다면 break를 통해 반복문을 탈출하고 이동한 총 거리를 출력해 주었다.

 

💻 코드

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static int[] dy = {-1, 0, 0, 1};
    static int[] dx = {0, -1, 1, 0};
    static int[][] map;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        map = new int[N][N];
        int[] cur = null;

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 9) {
                    cur = new int[]{i, j};
                    map[i][j] = 0;
                }
            }

        int size = 2;
        int eat = 0; // 먹은 물고기 수
        int move = 0; // 움직인 총 거리

        while (true) {
            PriorityQueue<int[]> que = new PriorityQueue<>((o1, o2) ->
                    o1[2] != o2[2] ? Integer.compare(o1[2], o2[2]) : (o1[0] != o2[0] ? Integer.compare(o1[0], o2[0]) : Integer.compare(o1[1], o2[1]))
            );
            boolean[][] visit = new boolean[N][N];

            que.add(new int[]{cur[0], cur[1], 0}); // y좌표, x좌표, 이동한 거리
            visit[cur[0]][cur[1]] = true;

            boolean ck = false; // 상어가 먹이를 먹었는지 체크할 변수

            while (!que.isEmpty()) {
                cur = que.poll();

                if (map[cur[0]][cur[1]] != 0 && map[cur[0]][cur[1]] < size) { // 먹이가 있으면서 상어의 사이즈보다 작다면?
                    map[cur[0]][cur[1]] = 0; // 물고기를 제거
                    eat++; 
                    move += cur[2]; // 움직인 거리를 총 움직인 거리에 추가
                    ck = true; // 먹이 먹었다고 체크
                    break;
                }

                for (int k = 0; k < 4; k++) {
                    int ny = cur[0] + dy[k];
                    int nx = cur[1] + dx[k];

                    if (ny < 0 || nx < 0 || nx >= N || ny >= N || visit[ny][nx] || map[ny][nx] > size)
                        continue;

                    que.add(new int[]{ny, nx, cur[2] + 1});
                    visit[ny][nx] = true;
                }
            }

            if (!ck) // 큐가 비워질 때까지 먹이를 먹은적이 없다면, 더 이상 먹은 물고기가 없으므로 탈출
                break;

            if (size == eat) { // 사이즈와 먹이를 먹은 수가 동일하다면 상어의 크기를 증가
                size++;
                eat = 0;
            }
        }


        System.out.println(move);

    }


}

 

📊 제출 결과