백준 16236_아기 상어_JAVA

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

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

public class Main {
    static int N, sharkX, sharkY;
    static int[][] grid;
    static int[][] distance;
    static int sharkSize = 2;
    static int eatCount = 0;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int minX = 0;
    static int minY = 0;
    static int minDist = Integer.MAX_VALUE;
    static int moveCount = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        grid = new int[N][N]; // 그래프

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
                if (grid[i][j] == 9) { // 시작 좌표 저장
                    sharkX = i;
                    sharkY = j;
                    grid[i][j] = 0;
                }
            }
        }

        while (true) {
            distance = new int[N][N]; // 거리 배열 초기화
            minX = Integer.MAX_VALUE; // 상어에서 가장 가까이 있는 먹을 수 있는 물고기 X좌표
            minY = Integer.MAX_VALUE; // 상어에서 가장 가까이 있는 먹을 수 있는 물고기 Y좌표
            minDist = Integer.MAX_VALUE; // 상어에서 먹을 수 있는 가장 가까이 있는 물고기 거리

            bfs(sharkX, sharkY); // 가장 가까이 있는 먹을 수 있는 물고기 거리를 찾기 위해 bfs 사용

            // 위에 minX와 minY가 바뀌었다는건 bfs에서 먹을 수 있는 물고기를 찾았다는 것
            if (minX != Integer.MAX_VALUE && minY != Integer.MAX_VALUE) {
                eatCount++; // 먹은 물고기 +1
                grid[minX][minY] = 0; // 물고기를 먹었으니까 해당 좌표는 0으로 변경
                sharkX = minX;
                sharkY = minY;
                moveCount += distance[minX][minY];

                if (eatCount == sharkSize) { // 물고기를 먹은 횟수가 상어의 크기와 같아지면
                    sharkSize++; // 상어 크기 +1
                    eatCount = 0; // 먹은 횟수 0으로 초기화
                }
            } else {
                break;
            }
        }

        System.out.print(moveCount);
    }

    private static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int cur_x = cur[0];
            int cur_y = cur[1];

            for (int i = 0; i < 4; i++) {
                int next_x = cur_x + dx[i];
                int next_y = cur_y + dy[i];
                // distance == 0 이면 방문하지 않은곳
                if (next_x >= 0 && next_y >= 0 && next_x < N && next_y < N
                        && sharkSize >= grid[next_x][next_y] && distance[next_x][next_y] == 0) {
                    // 거리 배열에 최소 거리 입력
                    distance[next_x][next_y] = distance[cur_x][cur_y] + 1;
                    // 해당 위치에 물고기가 있고 상어보다 크기가 작은 물고기면?
                    if (grid[next_x][next_y] < sharkSize && grid[next_x][next_y] != 0) {
                        if (minDist > distance[next_x][next_y]) { // minDist보다 더 가까운 물고기라면?
                            minDist = distance[next_x][next_y]; // 최소 거리 갱신
                            minX = next_x;
                            minY = next_y;
                        } else if (minDist == distance[next_x][next_y]) { // 최소 거리인 물고기가 많으면?
                            if (minX == next_x) { // 위로 높이가 같으면?
                                if (minY > next_y) { // 더 왼쪽에 있는 물고기 선택 (y가 더 작아야 왼쪽에 있는거니까)
                                    minX = next_x;
                                    minY = next_y;
                                }
                            } else if (minX > next_x) { // 더 위에 있는 물고기라면?
                                minX = next_x;
                                minY = next_y;
                            }
                        }
                    }
                    queue.add(new int[]{next_x, next_y});
                }
            }
        }
    }
}

 

회고

- 조건이 너무 많아서 정말 까다로웠고 블로그들을 참고해서 풀었다.

- 다시 풀어봐야겠다.