[ 백준 / BOJ 16236 ] 아기 상어 ( 자바/JAVA )

문제 설명

아기 상어

• 처음 크기 : 2
• 1초에 상하좌우로 인접한 한 칸씩 이동 가능
• 자기보다 큰 물고기가 있는 곳은 통행 불가
• 자기보다 작은 물고기만 먹을 수 있다.
• 자기 크기 만큼 물고기를 먹으면 크기 += 1

아기 상어가 어디로 이동할지 결정하는 방법

• 더 이상 먹을 수 있는 물고기 ❎ 👉 엄마 상어에게 도움 요청
• 먹을 수 있는 물고기 1마리 👉 그 물고기 먹으로 가기
• 먹을 수 있는 물고기가 2마리 이상 👉 가장 가까운 물고기 먹으러 가기
  • 거리가 같은 물고기가 존재하면 👉 가장 위에 있는 물고기,
  • 그것도 여러 마리라면 👉 가장 왼쪽에 있는 물고기를 먹는다.

문제 풀이

1. 입력받기

map[i][j] : 공간의 상태
sharkX, sharkY : 아기 상어의 위치

2. 먹을 수 있는 물고기 탐색

checkMinDist(sharkX, sharkY)

BFS이용
dist[x][y] 👉 (sharkX, sharkY)부터 (x,y)까지 최소거리
map[x][y]에 물고기가 존재하고, 크기가 아기 상어보다 작으면,
👉 (minX, minY), minDist에 (x,y), dist[x][y] 저장

minDist가 같으면 가장 위에 있는 물고기, 그것도 같으면 가장 왼쪽 물고기의 위치 저장

3. 물고기 먹기

eatFish()
만약 (minX, minY)가 초기값이라면 더 이상 먹을 물고기 존재❌ 👉 종료

아기 상어가 먹은 물고기 수를 증가
(sharkX, sharkY)를 (minX, minY)로 변경
걸린 시간 time += minDist

아기 상어가 본인 크기만큼 물고기를 먹었다면, 크기 증가

코드

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

public class Main_BOJ_16236_아기_상어 {

    static int N, sharkX, sharkY, minX, minY, minDist, sharkSize = 2, eating = 0, time = 0;
    static int[][] map, dist;
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};

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

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

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

        while(true){
            dist = new int[N][N];
            minX = Integer.MAX_VALUE;
            minY = Integer.MAX_VALUE;
            minDist = Integer.MAX_VALUE;

            checkMinDist(sharkX, sharkY);
            if(eatFish()) break;
        }
        System.out.println(time);
    }

    private static boolean eatFish() {
        if (minX != Integer.MAX_VALUE && minY != Integer.MAX_VALUE) {
            eating++;
            map[minX][minY] = 0;
            sharkX = minX;
            sharkY = minY;
            time += dist[minX][minY];

            if (eating == sharkSize) {
                sharkSize++;
                eating = 0;
            }
            return false;
        }
        return true;
    }

    private static void checkMinDist(int sharkX, int sharkY) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{sharkX, sharkY});

        while (!q.isEmpty()) {
            int[] now = q.poll();

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

                if(nx < 0 || ny < 0 || N <= nx || N <= ny || map[nx][ny] > sharkSize || dist[nx][ny] != 0) continue;

                dist[nx][ny] = dist[now[0]][now[1]] + 1;


                if(map[nx][ny] != 0 && map[nx][ny] < sharkSize){
                    if(minDist > dist[nx][ny]){
                        minDist = dist[nx][ny];
                        minX = nx;
                        minY = ny;
                    } else if (minDist == dist[nx][ny]) {
                        if (minX == nx) {
                            minY = Math.min(minY, ny);
                        } else if (minX > nx) {
                            minX = nx;
                            minY = ny;
                        }
                    }
                }

                q.offer(new int[]{nx, ny});
            }
        }
    }
}