[Algorithm] 백준_16236 아기 상어

문제

아기상어가 이동하면서 자기 자신보다 값이 작은 물고기들을 잡아먹는데, 이 물고기를 최대한 잡아먹을 수 있는 시간을 구하는 문제이다.

문제 조건 😑.. Too Much..

1. 공간은 N*N이고, 물고기 M마리와 상어 한 마리가 있다. 둘 다 자연수의 크기를 가진다.
2. 아기 상어는 상하 좌우로 이동할 수 있다.
   2-1. 자신의 크기보다 작은 물고기만 먹을 수 있다.
   2-2. 크기가 같은 물고기는 먹을 수 없지만 지나갈 수 있다.
3. 먹을 수 있는 물고기가 1마리 이상이면, 거리가 가장 가까운 물고기를 먹으러 간다.
   3-1. 거리가 같은 물고기가 많으면 가장 위, 그 다음은 왼쪽을 우선순위로 한다.
4. 아기 상어가 자신의 크기와 같은 수의 물고기를 먹으면
   4-1. 크기가 1씩 증가한다. (아기 상어의 초기값은 2)
   4-2. 먹은 물고기의 칸은 0이 된다.

해결 방안

• 물고기와 아기상어의 최단 경로 구하기
  최단 경로 구하는데에는 BFS 알고리즘을 사용한다.
• 거리를 구한 뒤 먹을 수 있는 우선순위를 따진다.

소스 코드

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

public class Main {
    static int shark = 2;
    static int eatFish = 0; //먹은 물고기 수
    static int count = 0; //소요 시간
    static int[][] fishDistance; //거리와 방문 여부 체크
    static int[][] map;
    static int N;
    static Point start; //상어 위치
    static int minDist, minX, minY;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};

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

        map = new int[N][N];
        fishDistance = new int[N][N];

        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) {
                    start = new Point(i, j);
                    map[i][j] = 0;
                }
            }
        }

        while(true) {
            init();
            bfs(start.x, start.y);

            if (minX != Integer.MAX_VALUE && minY != Integer.MAX_VALUE) {
                count += fishDistance[minX][minY];
                eatFish++;

                if (eatFish == shark) {
                    shark++;
                    eatFish = 0;
                }

                map[minX][minY] = 0;

                start.x = minX;
                start.y = minY;
            } else {
                break;
            }
        }
        System.out.println(count);
    }

    /* 최소 거리와 그를 충족하는 좌표를 초기화한다. */
    public static void init() {
        minDist = Integer.MAX_VALUE;
        minX = Integer.MAX_VALUE;
        minY = Integer.MAX_VALUE;

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++) {
                fishDistance[i][j] = -1;
            }
        }
    }

    public static void bfs(int x, int y) {
        Queue<Point> q = new LinkedList<>();
        fishDistance[x][y] = 0;
        q.add(new Point(x, y));

        while(!q.isEmpty()) {
            Point p = q.poll();
            x = p.x;
            y = p.y;

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

                /* 범위 체크 & 방문 체크 & shark보다 큰지 */
                if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
                    continue;
                }
                if(map[nx][ny] > shark || fishDistance[nx][ny] != -1 ){
                    continue;
                }

                fishDistance[nx][ny] = fishDistance[x][y] + 1;

                //먹을 수 있는 물고기
                if( map[nx][ny] >= 1 && map[nx][ny] <= 6 && map[nx][ny] < shark ) {
                    if(minDist > fishDistance[nx][ny]){
                        minX = nx;
                        minY = ny;
                        minDist = fishDistance[nx][ny];
                    }
                    else if(minDist == fishDistance[nx][ny]){
                        if(minX == nx){
                            if(minY > ny){
                                minX = nx;
                                minY = ny;
                            }
                        } else if(minX > nx){
                            minX = nx;
                            minY = ny;
                        }
                    }
                }
                q.add(new Point(nx, ny));
            }
        }
    }

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

후기...

조건이 많아서 복잡했다.. 아직은 문제 이해도 힘들어..
우선순위 큐를 사용해서 해결하는 방식도 있을 것 같은데, 좀 더 깊이 생각해봐야 할 것 같다.

그리고 내가 간과한 부분은 처음에 map에 물고기와 아기상어를 입력받으면서, 9이면 (아기 상어이면) map의 해당 좌표를 0으로 만들어줘야 한다는 것이다. 이렇게 안하면 9를 물고기로 인식해서 count가 더 들어간다.

물고기 식별 조건에서 해당 값이 0이 아닐때 로 하지않고 값이 1보다 같거나 크고, 6보다 같거나 작으면으로 해도 될 것 같다~