[Gold III][JAVA] 16236번:아기상어

[삼성 기출 문제] 백준 16236 아기 상어

[Gold III] 16236번:아기상어 - 문제 풀러가기

종료조건

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.

먹는 조건

• 가장 처음아기 상어의 크기는 2이다.
• 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.

성장조건

• 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

이동 조건

• 1초에 상하좌우로 인접한 한 칸씩 이동
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

거리가 가까운 물고기 여러 마리 -> 상단
상단에 여러 마리 -> 왼쪽

=> 테스트 케이스 3번에서 주의할 점
이 기준이 BFS검사할떄 위 왼쪽 오른쪽 아래 기준이 아니라 배열 전체 기준으로 위, 왼쪽을 기준으로 해야됩니다

문제 접근 Tip

1. 최단경로 => BFS - 시작 정점에서 가까운 정점부터 차례대로 탐색
2. BFS + queue 함께 사용

dx, dy는 x, y 좌표의 변화량이므로 상하좌우 네 방향에 대해서는 다음 값을 가집니다.

    static int[] dx = {0, 0 , -1 ,1}; // 상 하 좌 우
    static int[] dy = {-1, 1, 0, 0};

TestCase

a. 처음 상어의 위치에서 먹을 수 있는 물고기는 [1], [2]로 거리는 동일하지만,
위치 우선순위상 [1]쪽으로 먼저간다. → Total Distance: 3
b. 아직 상어의 크기는 2이므로 [2]로 이동한다. 크기 Up(=3) → Total Distance: 3 + 6 = 9
c. 바로 오른쪽 [3]의 위치로 간다. → Total Distance: 9 + 1 = 10

d. 그 다음 유일한 먹이인 [4]의 위치로 간다. → Total Distance: 10 + 4 = 14
e. 상어의 크기보다 작은 물고기가 없으므로 종료

정답

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 {
    static int N, sharkRow, sharkCol, sharkSize = 2, eatCnt = 0;
    static int answer = 0; // 결과값
    static int map[][];
    static int[] dx = {0, 0, -1, 1}; // 상 하 좌 우
    static int[] dy = {-1, 1, 0, 0};
    static boolean[][] visited;
    static Queue<Node> queue;

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

        N = Integer.parseInt(br.readLine());
        map = 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) { // 상어인 경우
                    sharkRow = i;
                    sharkCol = j;
                    map[i][j] = 0;
                }
            }
        }
        while (true) {
            if (!BFS()) break;
        }
        System.out.println(answer);
    }

    private static boolean BFS() {
        visited = new boolean[N][N];
        queue = new LinkedList<>();

        queue.add(new Node(sharkRow, sharkCol, 0));
        visited[sharkRow][sharkCol] = true;
        int minDistance = Integer.MAX_VALUE;
        int minX = N, minY = N;

        while (!queue.isEmpty()) {
            Node node = queue.poll();

            if (node.distance > minDistance) break; // 더 이상 탐색할 필요 없음

            for (int i = 0; i < 4; i++) { // 상하좌우 방향
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                int dis = node.distance + 1;

                if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[nx][ny] && map[nx][ny] <= sharkSize) {
                    visited[nx][ny] = true;
                    queue.add(new Node(nx, ny, dis));

                    // 물고기를 찾은 경우
                    if (map[nx][ny] > 0 && map[nx][ny] < sharkSize) {
                        if (dis < minDistance) {
                            minDistance = dis;
                            minX = nx;
                            minY = ny;
                        } else if (dis == minDistance) {
                            if (nx < minX || (nx == minX && ny < minY)) {
                                minX = nx;
                                minY = ny;
                            }
                        }
                    }
                }
            }
        }

        if (minX != N && minY != N) { // 먹을 수 있는 물고기가 있는 경우
            map[minX][minY] = 0; // 물고기 먹기
            sharkRow = minX;
            sharkCol = minY;
            eatCnt++;

            if (eatCnt == sharkSize) { // 상어 크기 증가
                sharkSize++;
                eatCnt = 0;
            }

            answer += minDistance;
            return true;
        }

        return false; // 더 이상 먹을 물고기가 없는 경우
    }

    public static class Node {
        int x, y, distance;

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