백준 16236 : 아기 상어 [JAVA]

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

16236번: 아기 상어

1. 문제 설명

2. 문제 풀이

구현 해야 할 것

• 보드에서 상어 위치 찾기
• 먹을 수 있는 물고기의 거리와 자리를 넣은 리스트 만들기 (bfs)
• 그중 거리, x축, y축으로 정렬하여 가장 근접한 물고기 찾고 상어 위치 바꾸기
• 바꿀 때마다 거리를 초로 계산해 더해주어 답 구하기

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static int n, size, eat;
    static int board[][];
    static int dx[] = {-1, 0, 0, 1};
    static int dy[] = {0, -1, 1, 0};

    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];
        StringTokenizer st;
        int a = 0;
        int b = 0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] == 9) {
                    a = i;
                    b = j;
                    board[i][j] = 0;
                }
            }
        }
        size = 2;
        eat = 0;
        int cnt = 0;


        while (true) {
            ArrayList<int []> res = bfs(a, b);
            if (res.isEmpty()) {
                break;
            }
            int arr[] = res.get(0);
            for (int i = 0; i < res.size(); i++) {
                if (arr[0] > res.get(i)[0]) {
                    arr = res.get(i);
                } else if (arr[0] == res.get(i)[0]) {
                    if (arr[1] > res.get(i)[1]) {
                        arr = res.get(i);
                    } else if (arr[1] == res.get(i)[1]) {
                        if (arr[2] > res.get(i)[2]) {
                            arr = res.get(i);
                        }
                    }
                }
            }
            cnt += arr[0];
            a = arr[1];
            b = arr[2];

            board[a][b] = 0;
            eat += 1;
            if (size == eat) {
                size += 1;
                eat = 0;
            }
        }
        
        System.out.println(cnt);
    }

    static ArrayList<int []> bfs(int a, int b) {
        ArrayList<int []> res = new ArrayList<>();
        Queue<int []> queue = new LinkedList<>();
        queue.offer(new int[]{a, b});
        int visited[][] = new int[n][n];
        visited[a][b] = 1;

        while (!queue.isEmpty()) {
            int arr[] = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = arr[0] + dx[i];
                int ny = arr[1] + dy[i];

                if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
                    continue;
                }
                if (board[nx][ny] > size) {
                    continue;
                }
                if (board[nx][ny] != 0 && board[nx][ny] < size && visited[nx][ny] == 0) {
                    res.add(new int[]{visited[arr[0]][arr[1]], nx, ny});
                    visited[nx][ny] = visited[arr[0]][arr[1]] + 1;
                }
                if (visited[nx][ny] == 0) {
                    queue.offer(new int[]{nx, ny});
                    visited[nx][ny] = visited[arr[0]][arr[1]] + 1;
                }
            }
        }

        return res;
    }

}