글 읽기 - 아기상어 / 자바 시간초과 18%

kmn4555 4년 전 0

자바로 코드짰는데 18 퍼센트에서 계속 시간초과가 나오네요 ㅠㅠ

어디를해야 빠르게할 수 있을까요

방법은 bfs돌면서 거리 / y좌표 / x좌표를 우선순위로 우선순위큐에넣고 먹이를 찾다가 먹이가 없거나 q가 비면(먹을 수 있는 먹이가 없거나) 그러면 끝내는거로 했습니다.

반례는 전부 맞았는데 시간초과가 뜨네요ㅠ

import java.util.*;
import java.io.*;

public class Main {
	
	static BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	static String[] str;
	
	static int size;
	static int map[][];
	static boolean visit[][];
	
	static int addx[] = {0, -1, 1, 0};
	static int addy[] = {-1, 0, 0, 1};
	
	static int nowx, nowy;
	static int mysize = 2;
	static int feed = 0;
	
	static int feedn;
	
	static int time = 0;
	
	static class feed implements Comparable<feed>{
		int x, y, dist;
		
		public feed(int a, int b, int c) {
			this.x = a;
			this.y = b;
			this.dist = c;
		}
		
		public int getx() {
			return this.x;
		}
		public int gety() {
			return this.y;
		}
		public int getdist() {
			return this.dist;
		}
		
		@Override
		public int compareTo(feed target) {
			if(this.dist > target.getdist()) return 1;
			else if(this.dist < target.getdist()) return -1; 
			
			if(this.y == target.gety()) {
				if(this.x > target.getx()) return 1;
				else return -1;
			}
			else {
				if(this.y > target.gety()) return 1;
				else return -1;
			}
		}
	}
	
	static PriorityQueue<feed> q = new PriorityQueue<>();
	
	//크기가 같은 물고기는 지나갈 수 있지만 먹을수 없음.
	//크기가 작은 물고기는 먹을수 있고 먹으면 빈 칸이 됨.
	//크기가 큰 물고기는 지나갈 수 없음.
	

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		str = bfr.readLine().split(" ");
		size = Integer.parseInt(str[0]);
		
		map = new int[size][size];
		visit = new boolean[size][size];
		
		for(int i = 0; i < size; i++) {
			str = bfr.readLine().split(" ");
			for(int j = 0; j < size; j++) {
				map[i][j] = Integer.parseInt(str[j]);
				if(map[i][j] == 9) {
					nowx = j;
					nowy = i;
					map[i][j] = 0;
				}
				else if((map[i][j] >= 1) && (map[i][j] <= 6)) feedn++;
			}
		}
		
		bfs();
		
		bfw.write(time + "");
		bfw.flush();
	}
	
	static void bfs() {
		if(feedn == 0) return;
		int t = 0;
		visit[nowy][nowx] = true;
		q.clear();
		
		if(feedn == 0) return;
		
		q.offer(new feed(nowx, nowy, t));
		
		while(!q.isEmpty()) {
			int s = q.size();
			t++;
			for(int i = 0; i < s; i++) {
				feed f = q.poll();
				nowx = f.getx();
				nowy = f.gety();
				visit[nowy][nowx] = true; 
				
				if((map[nowy][nowx] > 0) && (map[nowy][nowx]< mysize)) {
					visit = new boolean[size][size];
					time += f.getdist();
					map[nowy][nowx] = 0;
					feed++;
					feedn--;
					if(feed == mysize) {
						mysize++;
						feed = 0;
					}
					bfs();
					return;
				}
				
				for(int j = 0; j < 4; j++) {
					int nextx = nowx + addx[j];
					int nexty = nowy + addy[j];
					
					if((nextx >= size) || (nextx < 0) || (nexty >= size) || (nexty < 0)) continue;
					if(visit[nexty][nextx]) continue;
					if(map[nexty][nextx] > mysize) continue;
					
					q.offer(new feed(nextx, nexty, t));
				}
			}
		}
	}
}