[백준] 16236 아기상어 - JAVA

1. 문제유형 : BFS (완전탐색)

2. 시간복잡도 : O(N^4)

 

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 {

	static int[] dy = { -1, 0, 1, 0 }; // 상 우 하 좌
	static int[] dx = { 0, 1, 0, -1 };

	static class Fish implements Comparable<Fish> {
		int x;
		int y;
		int dist;

		public Fish(int x, int y, int dist) {
			super();
			this.x = x;
			this.y = y;
			this.dist = dist;
		}

		@Override
		public int compareTo(Fish o) {
			if(dist > o.dist) {
				return 1;
			}else if(dist == o.dist) {
				if(y > o.y) return 1;
				if(y == o.y) return x - o.x;
			}
			return -1;
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int N = Integer.parseInt(in.readLine());
		int[][] map = new int[N][N];
		int[] pos = new int[2];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; j++) {
				int temp = Integer.parseInt(st.nextToken());
				if (temp == 9) {
					pos[1] = i; // y
					pos[0] = j; // x
				}
				map[i][j] = temp;
			}
		}
		System.out.println(eat(map, pos));
	}

	public static int eat(int[][] map, int[] initPos) {
		Fish shark = new Fish(initPos[0], initPos[1], 0);
		map[initPos[1]][initPos[0]] = 0;
		int size = 2;
		int time = 0;
		int amount = 0;
		
		while(true) {
			PriorityQueue<Fish> pq = new PriorityQueue<>(); // 먹을 수 있는 물고기를 담아두는 우선순위 큐 (거리 최소, 좌상을 우선순위로)
			boolean[][] visited = new boolean[map.length][map.length];
			Queue<Fish> pos = new LinkedList<>();
			pos.offer(shark);
			visited[shark.y][shark.x] = true;
			
			while(!pos.isEmpty()) {
				Fish current = pos.poll();	// 현재 상어 위치
				for (int i = 0; i < 4; i++) {
					int nextX = current.x + dx[i];
					int nextY = current.y + dy[i];
					if (nextX >= 0 && nextX < map.length && nextY >= 0 && nextY < map.length) {
						int fishSize = map[nextY][nextX];
						if(visited[nextY][nextX] || fishSize > size) continue;
						visited[nextY][nextX] = true;
						pos.offer(new Fish(nextX, nextY, current.dist+1));
						if (fishSize !=0 && fishSize != 9 && fishSize < size) {
							// 물고기가 있다면 우선순위 큐에 넣음
							pq.offer(new Fish(nextX, nextY, current.dist+1));
						}
					}
				}
			}
			
			// 탐색이 다 끝나고
			if(pq.isEmpty()) {
				// 먹을 수 있는 물고기가 없다면 종료
				return time;
			}
			
			// 먹을 수 있는 물고기가 있다면
			Fish fish = pq.poll();
			time += fish.dist;
			if(++amount == size) {
				size++;
				amount = 0;
			}
			
			// 상어 위치 이동
			map[fish.y][fish.x] = 0;
			shark = new Fish(fish.x, fish.y, 0);
		}
	}

}