[BOJ] 백준 16236 아기 상어

[문제]

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

 

 

[소스 코드]

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

public class Main {
	static int[] shark = new int[2];
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		int[][] 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) {
					shark[0] = i;
					shark[1] = j;
					map[i][j] = 0;
				}
			}
		}
		int size = 2;
		int eat = 0;
		int time = 0;
		while(true) {
			PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[2]!=b[2]?a[2]-b[2]:a[0]!=b[0]?a[0]-b[0]:a[1]-b[1]);
			boolean[][] visit = new boolean[n][n];
			visit[shark[0]][shark[1]] = true;
			pq.offer(new int[] {shark[0],shark[1],0});
			boolean check = false;
			while(!pq.isEmpty()) {
				int[] curr = pq.poll();
				if(map[curr[0]][curr[1]]!=0 && map[curr[0]][curr[1]]<size) {
					eat++;
					shark[0] = curr[0];
					shark[1] = curr[1];
					time += curr[2];
					map[curr[0]][curr[1]] = 0;
					check = true;
					break;
				}
				for(int d=0;d<4;d++) {
					int nr = curr[0] + dr[d];
					int nc = curr[1] + dc[d];
					if(nr<0 || nr>=n || nc<0 || nc>=n || visit[nr][nc] || map[nr][nc]>size) continue;
					visit[nr][nc] = true;
					pq.offer(new int[] {nr,nc,curr[2]+1});
				}
			}
			if(!check) break;
			if(size==eat) {
				size++;
				eat = 0;
			}
		}
		System.out.println(time);
	}
}