백준 16236번 : 아기 상어[java]

1. 상어의 위치에서 bfs를 시작해 최단 거리에 있는 먹을 수 있는 물고기의 위치를 모두 저장해둡니다.

→ 모든 위치를 저장하는 이유는 하나의 최단거리를 발견하자마자 이동하면 가장 위쪽 우선, 가장 왼쪽 우선이라는
조건을 만족하지 않을 수 있기 때문에 모든 위치를 저장한 후 비교하여 이동할 위치를 결정합니다.

 

2. 다음으로 이동할 곳이 없거나 먹을 수 있는 물고기가 없을 때 까지 1번을 반복합니다.

 

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

public class Main{
	
	static class P implements Comparable<P>{
		int x=0;
		int y=0;
		int t=0;
		public P(int X, int Y, int T) {
			x = X;
			y = Y;
			t = T;
		}
		@Override
		public int compareTo(P o) {
			if(this.t != o.t) {
				return this.t - o.t;
			}
			if(this.y != o.y) {
				return this.y - o.y;
			}
			return this.x - o.x;
		}
	}
	
	// 위 > 왼 > 오른 > 아래 방향 순서로 탐색
	static int[] dx = {0,-1,1,0};
	static int[] dy = {-1,0,0,1};
	
	static int[][] map;
	static boolean[][] check;
	
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        P shark = new P(0,0,0); // 상어의 위치
        int size = 2; // 상어의 크기
        int count = 0; // 상어가 먹은 물고기의 수
        int time = 0; // 걸린 시간
        map = new int[N][N];
        check = new boolean[N][N];
        for(int y=0; y<N; y++) {
        	String[] str = br.readLine().split(" ");
        	for(int x=0; x<N; x++) {
        		int n = Integer.parseInt(str[x]);
        		if(n == 9) {
        			shark = new P(x,y,0);
        			map[y][x] = 0;
        		}
        		else {
            		map[y][x] = n;
        		}
        	}
        }
        
        //bfs 시작
        Queue<P> move = new LinkedList<>();
        move.add(shark);
        check[shark.y][shark.x] = true;
        
        boolean found = false;
        PriorityQueue<P> fish = new PriorityQueue<>(); // 먹이 후보
        // System.out.println("x: "+shark.x+ "  y: "+shark.y+"  size: "+size+"  count: "+count+"  time: "+time);
        while(!move.isEmpty() || !fish.isEmpty()) {
        	P p;
        	if(!move.isEmpty()) {
            	p = move.poll();
        	}
        	else {
        		p = new P(100,100,100);
        	}
        	if(found) {
        		if(p.t >= fish.peek().t || move.isEmpty()) {
                        P next = fish.poll();
                        fish.clear();
                        found = false;
                        map[next.y][next.x] = 0;
    				check = new boolean[N][N];
    				check[next.y][next.x] = true;
    				time += next.t;
    				shark = new P(next.x,next.y,0);
    				move.clear();
    				move.add(shark);
                    		// 물고기를 크기만큼 먹었다면
    				if(++count == size) { 
    					count = 0;
    					size++;
    				}
    				// System.out.println("x: "+next.x+ "  y: "+next.y+"  size: "+size+"  count: "+count+"  time: "+time);
    				continue;
            		}
        	}
        	
        	for(int i=0; i<4; i++) {
        		int mx = p.x + dx[i];
        		int my = p.y + dy[i];
                	// map 안에 있는지 검사 + 방문여부 검사
        		if(mx>=0 && my>=0 && mx<N && my<N && !check[my][mx]) { 
                		// 먹을 수 있는 물고기 발견 > 먹이 후보에 넣어둔다
        			if(map[my][mx] < size && map[my][mx] != 0) { 
        				fish.add(new P(mx,my,p.t+1));
        				found = true;
        				check[my][mx] = true;
        			}
        			else if(map[my][mx] <= size) { // 이동
        				move.add(new P(mx,my,p.t+1));
        				check[my][mx] = true;
        			}
        		}
        	}
        }
        System.out.print(time);
    }
}