[BOJ 16236] 아기 상어 (Java)

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

16236번: 아기 상어

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_BOJ_16236 {
	static class Fish implements Comparable<Fish>{
		int r, c, size, d;
		Fish(int r, int c, int size, int d){
			this.r=r;
			this.c=c;
			this.size=size;
			this.d=d;
		}
		@Override
		public int compareTo(Fish o) {
			int dist=this.d-o.d;
			if (dist==0) {
				int diff_c=this.r-o.r;
				if (diff_c==0) return this.c-o.c;
				return diff_c;
			}
			return dist;
		}
	}
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static int N;
	static int[][] map;
	static int shark_size=2;
	static int shark_r, shark_c;
	static int cnt=0;		//먹은 횟수
	static int answer=0;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		N=Integer.parseInt(br.readLine());
		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_r=i; 
					shark_c=j;
				}
			}
		}
		while(true) {
			if (!findFish(new boolean[N][N])) break;
		}
		System.out.println(answer);
	}
	
	private static boolean findFish(boolean[][] visited) {
		PriorityQueue<Fish> pq=new PriorityQueue<>();
		Queue<int[]> q=new LinkedList<>();
		q.add(new int[] {shark_r, shark_c, 0});
		visited[shark_r][shark_c]=true;
		while (!q.isEmpty()) {
			int[] temp=q.poll();
			for (int d=0; d<4; d++) {
				int nr=temp[0]+dr[d];
				int nc=temp[1]+dc[d];
				if (nr<0 || nc<0 || nr>=N || nc>=N) continue;
				if (map[nr][nc]==0 || map[nr][nc]==shark_size){
					if (!visited[nr][nc]) {
						q.add(new int[] {nr,nc, temp[2]+1});
						visited[nr][nc]=true;
					}
				}
				else if (map[nr][nc]<shark_size && !visited[nr][nc]) {
					q.add(new int[] {nr,nc, temp[2]+1});
					visited[nr][nc]=true;
					pq.offer(new Fish(nr, nc, map[nr][nc], temp[2]+1));
				}
			}
		}
		if (pq.isEmpty()) return false;
		Fish f=pq.poll();
		map[f.r][f.c]=0;	//먹어치움
		answer+=f.d;
		cnt++;
		if (cnt==shark_size) {
			shark_size++;
			cnt=0;
		}
		map[shark_r][shark_c]=0;	//자리 옮김
		shark_r=f.r;
		shark_c=f.c;
		return true;
		
	}

}

Fish 객체는 fish의 r,c 위치, 사이즈, distance 값을 저장한다. 

Comparable 인터페이스를 구현해서 거리->row->col 순으로 비교가 가능하도록 설정해준다.

 

아기 상어 위치부터 시작해서, bfs 로 가장 가까운 물고기를 구해준다.

이때, bfs는 다음과 같이 동작한다.

-큐에서 빠져나온 아이템 중 인접 4 영역에 대해, 

방문하지 않았으면서 0 또는 shark_size 와 같은 애들에 대해 지나갈 수 있으므로 탐색 대상으로 큐에 넣어준다.

방문하지 않았으면서 shark_size와 작은 물고기 애들에 대해 이 역시 지나갈 수 있으므로 탐색 대상으로 큐에 넣어주고, 또 이 위치의 물고기는 우선순위 큐에 넣어준다.

 

N*N 영역에 대해 bfs 탐색이 끝나면, 우선순위 큐가 비었으면 더이상 먹을 물고기가 없으므로 종료한다.

우선순위 큐에 아이템이 존재하면 우선순위 큐에서 가장 처음에 튀어나온 물고기를 먹이 대상으로 삼고, 해당 위치를 0으로 설정하고, shark_size를 조건에 맞게 조정해주고, shark 위치를 바꿔주고 기존 위치는 0으로 표시해준다.

 

그런데 이렇게 하면 223ms? 정도로 조금 느렸다.

다른 분들의 풀이를 보니,  priority queue에 bfs 한번을 돌려준다.

https://rebas.kr/714

priority queue에 탐색 가능한 대상(미방문이며, 0<=size<=shark_size 인 애들)을 넣어주고, 큐에서 빠져나온 대상이 1<=size<shark_size 인 애들에 한해 그 물고기를 먹어주고, 큐를 비우고, 다시 bfs 탐색을 진행하는 방식이다.

빈칸이든, 어떤 사이즈를 가진 상어든 priority queue에 넣어주면 조건에 맞게 아이템이 튀어나오게 되고, 그 아이템이 1<=size<shark_size 인 애들이라면 조건에 맞게 가장 적절한 애가 튀어나오게 되고, 그 뒤에 있는 물고기들은 더이상 의미가 없으므로 큐를 비워주고 다시 먹은 물고기의 위치부터 탐색해주면 되는 것이다.