[BOJ] 16236 아기 상어

 

 

[문제]

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

 

 

[소스 코드]

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

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

 

주의: 기준 값이 존재하기 때문에, Queue에 넣고 확인 !

상어를 잡는 경우, bfs를 사용해서 가장 가까운 것 찾기