[백준/BOJ] 16236 아기 상어 - JAVA

[백준/BOJ] 16236 아기 상어 - JAVA

문제

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

 

문제 분석

조건

• NxN 공간에 물고기와 아기 상어가 있다.
• 상어는 자신보다 크기가 작은 물고기만 먹을 수 있고,
  크기가 같은 물고기는 지나갈 수만 있고,
  더 큰 물고기는 아예 지나가지 못한다.
• 한 번에 가장 가까운 물고기를 먹으러 간다.
  만약 거리가 같은 물고기가 여러 마리라면,
  ➝ 위쪽, 그다음 왼쪽 물고기를 우선으로 선택한다.
• 상어는 자신의 크기만큼 물고기를 먹을 때마다 크기가 1 증가한다.
• 모든 과정을 반복하며, 상어가 더 이상 먹을 물고기가 없을 때까지 걸리는 총 시간을 구하는 문제

풀이방법

• 가장 가까운 물고기를 구하기 위해 BFS를 사용한다. 그 과정에서 우선순위 큐를 활용하여 거리 -> 위쪽 -> 왼쪽 순으로 정렬되도록 정렬 기준을 정하고, 우선순위 큐를 사용한다.
• 먹을 수 있는 물고기가 있는 좌표를 구하는 `getNextPoint(현재 좌표)`를 사용하였다. `while`문에서 좌표값이 null로 나오기 전까지 반복한다.
• 물고기를 먹으면 해당 좌표에 물고기를 지우고 현재 사이즈와 먹은 물고기 수를 비교해 사이즈 조절을 해준다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Point implements Comparable<Point> {
    private int r, c, count;

    public Point(int r, int c, int count) {
        this.r = r;
        this.c = c;
        this.count = count;
    }

    public int getR() {
        return r;
    }

    public int getC() {
        return c;
    }

    public int getCount() {
        return count;
    }

    @Override
    public int compareTo(Point o) {
        if (this.count == o.count) {
            if (this.r == o.r) {
                return this.c - o.c;
            }
            return this.r - o.r;
        }
        return this.count - o.count;
    }
}

public class Main {
    static int nowSize, time, eatCount;
    static int[][] map;
    static int N;

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

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        int[] now = {0, 0};
        for (int r = 0; r < N; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; c++) {
                map[r][c] = Integer.parseInt(st.nextToken());
                if (map[r][c] == 9) {
                    now[0] = r;
                    now[1] = c;
                    map[r][c] = 0;
                }
            }
        }

        nowSize = 2;
        time = 0;
        eatCount = 0;
        while ((now = getNextPoint(now)) != null) {     // 이동 가능한 좌표가 있으면 반복
            eatCount++; //물고기 먹기
            map[now[0]][now[1]] = 0;
            if (eatCount == nowSize) {  // 사이즈 만큼 먹었을 경우 크기 자람
                nowSize++;
                eatCount = 0;
            }
        }
        System.out.println(time);
    }

    /**
     * 다음 이동할 좌표(먹어야하는 물고기가 있는 위치)를 구하는 함수
     *
     * @param now 현재 좌표
     * @return 다음 이동 좌표
     */
    private static int[] getNextPoint(int[] now) {
        boolean[][] visited = new boolean[N][N];
        // 거리순, 거리가 같다면 위쪽, 왼쪽 우선순위를 위해 우선순위 큐 사용
        PriorityQueue<Point> que = new PriorityQueue<>();
        que.add(new Point(now[0], now[1], 0));
        visited[now[0]][now[1]] = true;
        int[][] dirs = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
        while (!que.isEmpty()) {
            Point nowPoint = que.poll();

            // 잡아 먹을 수 있는 물고기가 있는 좌표면 좌표 반환
            if (map[nowPoint.getR()][nowPoint.getC()] > 0
                    && map[nowPoint.getR()][nowPoint.getC()] < nowSize) {
                time += nowPoint.getCount();    // 물고기까지 거리(이동시간) 더하기
                return new int[]{nowPoint.getR(), nowPoint.getC()};
            }
            for (int[] dir : dirs) {
                int nextR = nowPoint.getR() + dir[0];
                int nextC = nowPoint.getC() + dir[1];
                if (canMove(nextR, nextC) && !visited[nextR][nextC]) {    // 이동 가능하면 큐에 삽입
                    que.add(new Point(nextR, nextC, nowPoint.getCount() + 1));
                    visited[nextR][nextC] = true;
                }
            }
        }
        return null;
    }

    /**
     * 이동 가능한지 확인(범위 내 빈 곳이거나, 작거나 같은 사이즈의 물고기가 있는 곳)
     *
     * @param nextR
     * @param nextC
     * @return
     */
    private static boolean canMove(int nextR, int nextC) {
        if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= N
                || map[nextR][nextC] > nowSize) {
            return false;
        }
        return true;
    }

}

시간복잡도

BFS 한번 돌 때 마다 최대 맵의 크기인 O(N*N)만큼 소요된다.
먹이를 한번 먹으면 해당 위치에서 다시 탐색하므로 최대 물고기 수인 N*N만큼 반복된다.