백준 16236 아기상어 (Java)

1. 문제 링크

16236번: 아기 상어

 

2. 문제 및 입출력예제

 

3. 문제 풀이

BFS와 PriorityQueue를 이용해 풀었다.

현재 상어의 위치를 기준으로 사방으로 BFS 하면서 먹을 수 있는 크기인지 or 지나갈 수 있는 크기인지 확인해서 각각 PQueue와 Queue에 넣는다.

Point 클래스에 Comparable을 구현해서 정렬된 상태로 PQueue에 들어간다.

주의할 점은 맨해튼 거리를 사용하는 것이 아니고, 움직인 거리를 더해야 한다.

 

4. 코드

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

class Point implements Comparable<Point>{
    int x;
    int y;
    public Point(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }
    @Override
    public int compareTo(Point o) {
        if(this.x != o.x) {
        	return this.x - o.x;
        }
        else {
        	return this.y - o.y;
        }
    }
}

public class Main {
    static int N, sharkX, sharkY, sharkSize=2, answer, map[][], eat; 
	static boolean[][] visit; 
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};


	public static void main(String[] args) throws NumberFormatException, IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    N = Integer.parseInt(br.readLine());
	    
	    map = new int[N][N];
	    for(int i = 0; i < N; i++) {
	        String str[] = br.readLine().split(" ");
            for(int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(str[j]);
				if(map[i][j]==9) {
				 sharkX = i;
				   sharkY = j;
				   map[i][j] = 0;
				}
            }
        }

        while(simulate()) { }
        
        System.out.println(answer);
    }

    private static boolean simulate() {
        visit = new boolean[N][N];
        Queue<Point> queue = new ArrayDeque<Point>();
        queue.offer(new Point(sharkX, sharkY));
        visit[sharkX][sharkY] = true;
        PriorityQueue<Point> pq = new PriorityQueue<>();
        int depth = 0;
        while(!queue.isEmpty()) {
            int count = queue.size();
            depth++;
            while(count != 0) {
                Point current = queue.poll();
                count--;
                for(int d = 0; d < 4; d++) {
                    int X = current.x + dx[d];
                    int Y = current.y + dy[d];
                    if(X >= 0 && X < N && Y >= 0 && Y < N) {
                        if(!visit[X][Y] && map[X][Y] < sharkSize && map[X][Y] > 0) {
                            pq.offer(new Point(X, Y));
                            visit[X][Y] = true;
                        }
                        else if(!visit[X][Y] && (map[X][Y] == sharkSize || map[X][Y] == 0)) {
                            queue.offer(new Point(X, Y));
                            visit[X][Y] = true;
                        }
                    }
                }
            }
            if(pq.size() > 0) {
                Point temp = pq.poll();
                answer += depth;
                sharkX = temp.x;
                sharkY = temp.y;
                map[sharkX][sharkY] = 0;
                eat++;
                if(eat == sharkSize) {
                    sharkSize++;
                    eat = 0;
                }
                return true;
            }
        }
        return false;
    }
}