BOJ - 아기 상어 16236번 (JAVA)

❓ 문제 - 백준 아기 상어 16236번 - JAVA 풀이법

출처 

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

 

 

📝 문제해결법

1. 이 문제는 BFS + 구현으로 풀었다.

• 아기상어는 현재위치에서 BFS를 통해 거리가 가장 가깝고, 거리가 같으면 행이 가장 작고, 행이 같으면 열이 작은 물고기를 구한다. 만약 BFS에서 반환되는 값이 NULL, 즉 먹을 수 있는 물고기가 없으면 종료하고 값을 출력한다.
• BFS내에서 아기상어는 자기자신보다 작은 사이즈의 물고기에 대한 정보를 우선순위큐 pq에 넣고, 자기 자신과 크기가 같거나 자기 자신보다 크기가 작은 물고기를 지나갈 수 있으므로 지나다니면서 먹을 수 있는 물고기를 찾아 다닌다.
• 우선순위 큐에서 하나 꺼낸 게 아기상어가 먹으러가는 물고기 이므로 해당 물고기를 먹고, 아기상의 위치를 그 물고기의 위치로 변경시켜준다. 
• 만약 현재까지 먹은 물고기의 갯수가 현재 아기상어의 크기만큼이라면 아기상어의 크기는 1증가하고 현재까지 먹은 물고기 수를 0으로 리셋해준다.

 

 

💻 소스코드

// BOJ - 아기상어(16236번)
// 구현 + BFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main_16236{
	public static int n;
	public static int s_x, s_y, s_size;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	public static int[][] map;
	public static class Fish implements Comparable<Fish>{
		int x;
		int y;
		int dis;

		public Fish(int x, int y, int dis) {
			this.x = x;
			this.y = y;
			this.dis = dis;
		}
		@Override
		public int compareTo(Fish o) {
			// TODO Auto-generated method stub
			if(this.dis==o.dis) {
				if(this.x == o.x) {
					return this.y- o.y;
				}
				return this.x - o.x;
			} 
			return this.dis - o.dis;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		s_size = 2;
		for(int i=0;i<n;i++) {
			String[] data = br.readLine().split(" ");
			for(int j=0;j<n;j++) {
				map[i][j] = Integer.parseInt(data[j]);
				if(map[i][j] == 9) {
					map[i][j] = 0;
					s_x = i;
					s_y = j;
				} 
			}
		}
		
		int time = 0;
		int cnt = 0;
		while(true) {
			Fish fish = bfs();

			if(fish == null) {
				break;
			} else {
				map[fish.x][fish.y] = 0;
				s_x = fish.x;
				s_y = fish.y;
				cnt++;
				time += fish.dis;
				if(cnt == s_size) {
					cnt = 0;
					s_size++;
				} 
			}
	
		}
		
		System.out.println(time);

	}
	
	public static Fish bfs() {
		PriorityQueue<Fish> pq = new PriorityQueue<>();
		
		boolean[][] visited = new boolean[n][n];
		Queue<Fish> q = new LinkedList<>();
		q.add(new Fish(s_x, s_y, 0));
		visited[s_x][s_y] = true;
		int move_cnt = 0;
		while (!q.isEmpty()) {
			Fish fish = q.poll();

			for(int d=0;d<4;d++) {
				int nx = fish.x + dx[d];
				int ny = fish.y + dy[d];
				if(0 <= nx && nx < n && 0 <= ny && ny < n) {
					if(!visited[nx][ny] & map[nx][ny] <= s_size) {
						q.add(new Fish(nx, ny, fish.dis+1));
						visited[nx][ny] = true;
						if(map[nx][ny] != 0 && map[nx][ny] < s_size) {
							pq.add(new Fish(nx, ny, fish.dis+1));
						}
					}
				}
			}
			
		}
		if(pq.isEmpty()) {
			return null;
		}
		return pq.poll();
	}

}