(코테) 백준_16236_아기 상어 *조건 기반 BFS + 시뮬레이션 + 우선순위

 

 

package codingTest;

import java.util.*;

public class Backjun_testee {
    static int N;
    static int[][] map;
    static int[] dx = {-1, 0, 0, 1}; // 위, 왼, 오, 아래 (우선순위 맞추기 위함)
    static int[] dy = {0, -1, 1, 0};
    static int sharkSize = 2, eatCount = 0;
    static int time = 0;
    static int sx, sy; // 상어 위치

    static class Fish implements Comparable<Fish> {
        int x, y, dist;
        public Fish(int x, int y, int dist) {
            this.x = x; this.y = y; this.dist = dist;
        }
        public int compareTo(Fish o) {
            if (this.dist != o.dist) return this.dist - o.dist;
            if (this.x != o.x) return this.x - o.x;
            return this.y - o.y;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 9) {
                    sx = i;
                    sy = j;
                    map[i][j] = 0;
                }
            }
        }

        while (true) {
            Fish target = bfs();
            if (target == null) break; // 먹을 물고기 없으면 끝

            time += target.dist;
            eatCount++;
            if (eatCount == sharkSize) {
                sharkSize++;
                eatCount = 0;
            }
            // 상어 위치 이동 및 물고기 제거
            map[target.x][target.y] = 0;
            sx = target.x;
            sy = target.y;
        }

        System.out.println(time);
    }

    static Fish bfs() {
        boolean[][] visited = new boolean[N][N];
        Queue<Fish> q = new LinkedList<>();
        List<Fish> fishes = new ArrayList<>();
        q.add(new Fish(sx, sy, 0));
        visited[sx][sy] = true;

        while (!q.isEmpty()) {
            Fish cur = q.poll();

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

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

                visited[nx][ny] = true;
                int val = map[nx][ny];

                if (val > 0 && val < sharkSize) {
                    fishes.add(new Fish(nx, ny, cur.dist + 1));
                }

                q.add(new Fish(nx, ny, cur.dist + 1));
            }
        }

        if (fishes.isEmpty()) return null;

        Collections.sort(fishes); // 거리, 위, 왼 우선 정렬
        return fishes.get(0);
    }
}