백준 - 16236 아기 상어(Java)

구현 문제입니다.

 

문제 접근 순서는 다음과 같습니다.

1. 현재 위치에서 최소 경로로 갈 수 있는 곳을 확인하면서 먹을 수 있는 물고기를 가져옴
2. 먹을 물고기가 없다면 엄마 상어 호출
3. 먹을 수 있는 물고기중 가장 좌측 상단의 물고기를 가져와서 정보를 갱신함
4. 1번 부터 반복

 

현재 위치에서 다른 위치로가는 최소 경로는 다익스트라를 사용하시면 됩니다.

 

[구현 코드]

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

public class Main {
    private static final int[] dx = {-1, 0, 1, 0}; // 상, 좌, 하, 우
    private static final int[] dy = {0, -1, 0, 1};
    private static final int MAX = 987_654_321;

    private static int[][] map;
    private static int n;

    private static class Pisces implements Comparable<Pisces> {
        int x, y, dis;

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

        @Override
        public int compareTo(Pisces o) {
            if (this.dis == o.dis) {
                if (this.x == o.x) return this.y - o.y;
                return this.x - o.x;
            }
            return this.dis - o.dis;
        }
    }

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

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];

        int x = 0;
        int y = 0;
        for (int i = 0; i < n; i++) {
            stz = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(stz.nextToken());

                if (map[i][j] == 9) {
                    x = i;
                    y = j;
                    map[i][j] = 0;
                }
            }
        }

        int time = 0;
        int eat = 0;
        int size = 2;

        Queue<Pisces> qu = new LinkedList<>();
        Pisces nowShark = new Pisces(x, y, 0);
        qu.offer(nowShark);

        // 먹을 수 있을 때 까지 반복
        while (true) {
            // 현재 상어의 위치를 0으로 하고, 나머지를 MAX로 초기화
            int[][] distance = initDistance(nowShark);

            // 1. (다익스트라로) 현재 위치에서 최소 경로로 갈 수 있는 곳을 확인하면서 먹을 수 있는 물고기를 가져옴
            List<Pisces> foods = getFoods(size, qu, distance);

            // 2. 먹을 물고기가 없다면 엄마 상어 호출
            if (foods.size() == 0) {
                break;
            }

            // 아기상어 이동 방법 제약으로 인해 좌측 상단의 물고기를 먹을 수 있도록 함
            Collections.sort(foods);

            // 3. 먹을 수 있는 물고기중 가장 좌측 상단의 물고기를 가져와서 정보를 갱신함
            nowShark = foods.get(0);
            map[nowShark.x][nowShark.y] = 0;
            eat++;
            time += distance[nowShark.x][nowShark.y];

            if (size == eat) {
                eat = 0;
                size++;
            }
            qu.add(nowShark);
        }

        bw.write(String.valueOf(time));

        bw.flush();
        bw.close();
        br.close();
    }

    private static int[][] initDistance(Pisces nowShark) {
        int[][] distance = new int[n][n];

        for (int i = 0; i < n; i++) {
            Arrays.fill(distance[i], MAX);
        }
        distance[nowShark.x][nowShark.y] = 0;
        return distance;
    }

    private static List<Pisces> getFoods(int size, Queue<Pisces> qu, int[][] distance) {
        List<Pisces> foods = new ArrayList<>();
        
        while (!qu.isEmpty()) {
            Pisces cn = qu.poll();

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

                if (!inRange(nx, ny)) continue;
                if (map[nx][ny] > size) continue; // 이동할 수 없다면 스킵

                if (distance[nx][ny] > distance[cn.x][cn.y] + 1) {
                    distance[nx][ny] = distance[cn.x][cn.y] + 1;
                    Pisces nextShark = new Pisces(nx, ny, distance[nx][ny]);

                    qu.add(nextShark);
                    if (map[nx][ny] > 0 && map[nx][ny] < size) foods.add(nextShark); // 먹을 수 있다면
                }
            }
        }
        
        return foods;
    }


    private static boolean inRange(int x, int y) {
        return (x >= 0 && y >= 0 && x < n && y < n);
    }

}