[알고리즘/백준] 16236 아기 상어 - 자바(Java), 삼성 SW 역량테스트, 너비우선탐색(BFS)

문제

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

풀이코드

• 일반적인 BFS 풀이 방법에 추가적인 조건을 덧붙혀서 풀이해야되는 문제이다.
• BFS를 한번 진행할 때마다 상어가 이동 가능한 모든 곳을 탐색하며 먹을 수 있는 최단 거리의 물고기를 찾는데 만약 최단 거리가 같은 물고기가 여러개 있는 경우 더 위쪽에 있는 물고기를, 이 또한 같다면 더 왼쪽에 있는 물고기 한마리를 먹는다.

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

public class Main {

    static class Pos {
        int x;
        int y;

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

    static int[][] board, dist;
    static Pos shark = null;
    static int numOfFish = 0, n, sharkSize = 2, seconds = 0, eatFish = 0;
    static int minX, minY, minDist;

    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};

    public static void bfs() {
        Queue<Pos> q = new LinkedList<>();

        q.offer(shark);

        while (!q.isEmpty()) {
            Pos poll = q.poll();

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

                if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] <= sharkSize && dist[nx][ny] == 0) {
                    dist[nx][ny] = dist[poll.x][poll.y] + 1;

                    if (board[nx][ny] > 0 && board[nx][ny] < sharkSize) {
                        if (minDist > dist[nx][ny]) {
                            minDist = dist[nx][ny];
                            minX = nx;
                            minY = ny;
                        } else if (minDist == dist[nx][ny]) {
                            if (minX > nx) {
                                minX = nx;
                                minY = ny;
                            } else if(minX == nx) {
                                if (minY > ny) {
                                    minX = nx;
                                    minY = ny;
                                }
                            }
                        }
                    }

                    q.offer(new Pos(nx, ny));
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n][n];
        shark = null;

        StringTokenizer st = null;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < n; j++) {
                int num = Integer.parseInt(st.nextToken());

                if (num == 9 ) {
                    shark = new Pos(i, j);
                } else if (num > 0) {
                    board[i][j] = num;
                    numOfFish++;
                }
            }
        }

        while (true) {
            minX = Integer.MAX_VALUE;
            minY = Integer.MAX_VALUE;
            minDist = Integer.MAX_VALUE;
            dist = new int[n][n];

            bfs();

            if (minX == Integer.MAX_VALUE) {
                break;
            }

            eatFish++;
            board[minX][minY] = 0;
            shark.x = minX;
            shark.y = minY;
            seconds += dist[minX][minY];

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

        for (int i = 0; i < n; i++) {
            System.out.println(Arrays.toString(dist[i]));
        }

        System.out.println(seconds);
    }
}