BOJ - 16236 ) 아기상어

 

---

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

16236번: 아기 상어

 

---

당연히 푼문제인줄 알았었는데 C++로 풀었던문제여서 자바로 다시풀었다.

 

전체 먹을수있는 상어 후보(?)의 관리는 우선순위큐에관리하여 logN에 찾자.

 

한스텝마다, 우선순위큐에 먹을수있는 상어들을 뽑고, 그 상어까지의 최단거리 (BFS) 를통하여

 

처리한후, 그 상어가 있던 자리를 기준으로 다시 힙을 정렬한다.

 

이 과정을 더이상 먹을수 있는 상어가 없을때까지 진행한다.

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int map[][] = new int[n][n];
		int sy=0,sx=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) {
					sy = i ; sx = j;
					map[i][j] =0;
				}
			}
		}
		PriorityQueue<int []> pq = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// 거리가 가까운순서
				if(o1[2] < o2[2]) return -1;
				else if(o1[2] > o2[2]) return 1;
				else {
					// 같은경우 위쪽에 있는 y값이 작은
					if(o1[0] < o2[0]) return -1;
					else if(o1[0] > o2[0]) return 1;
					else {
						// 같은높이경우 왼쪽에있는 x 값이 작은
						if(o1[1] > o2[1]) return 1;
						else if(o1[1]< o2[1]) return -1;
						else return 0;
					}
				}
			}
		});
	
		int answer =0; int sharksize =2; int sharkeat =0;
		int dir[][] = {{1,0},{-1,0},{0,1},{0,-1}};
		
		ArrayDeque<int []> dq = new ArrayDeque<>();
		int visit[][] = new int[n][n];
		int mark=0;
		boolean isContinue = true;
		
		while( isContinue ){
			
			dq.add(new int []{sy,sx,0});
			mark++;
			while(!dq.isEmpty()) {
				int now [] = dq.poll();
				for(int i = 0 ; i < 4 ; i++) {
					int ny = now[0] +dir[i][0];
					int nx = now[1] +dir[i][1];
					if(ny >=0 && nx >=0 && nx < n &&  ny< n) {
						if(map[ny][nx] <= sharksize && visit[ny][nx]!=mark){
							visit[ny][nx] = mark;
							if(map[ny][nx]!=0 && map[ny][nx]<sharksize) {
								isContinue = true;
								pq.add(new int[] {ny,nx,now[2]+1});
							}
							dq.add(new int[] {ny,nx,now[2]+1});
						}
					}
				}
			}
			if(pq.isEmpty()) break;
			mark++;
			dq.add(new int[] {sy,sx,0});
			visit[sy][sx] =mark;
			int [] target = pq.poll();
				while(!dq.isEmpty()) {
					
					int now[] = dq.poll();
					if(now[0] == target[0] && now[1]== target[1]) {
						map[now[0]][now[1]] =0;
						sharkeat++;
						answer += now[2];
						dq.clear();
						break;
					} else {
						for(int i = 0 ; i < 4 ; i++) {
							int ny = now[0] + dir[i][0];
							int nx = now[1] + dir[i][1];
							if(ny >=0 && nx >=0 && ny < n && nx < n) {
								if(map[ny][nx] <= sharksize && visit[ny][nx] !=mark ) {
									visit[ny][nx] = mark;
									dq.add(new int[] {ny,nx,now[2]+1});
								}
							}
						}
					}
				}
						
				sy = target[0];
				sx = target[1];
				if(sharkeat == sharksize) {
					sharksize++;
					sharkeat =0;
				}
				pq.clear();
		}System.out.println(answer);
	}

}

---

C++가 역시 빠르다