글 읽기 - 아기상어 시간초과가 납니다.

jakyung8 5년 전 0

ㅠㅠ아기상어에서 시간초과가 되는데 왜 그런지를 모르겠습니다.. 방문처리도 전으로 했는데 왜 시간초과가 날까요..
package baekjoon;
import java.util.*;
public class P16236 {

	static int[][] ocean;
	static int[][] visit;
	static int n;
	static int[] dx= {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	static Queue<Shark> sharkqu = new ArrayDeque<Shark>();
	static Queue<Point> eatqu = new ArrayDeque<Point>();
	static Queue<Point> movequ = new ArrayDeque<Point>();
	
	public static void bfs(int x , int y, int size,int distance) {
		++distance;
	
		visit[x][y]=1;
		
		for(int i =0;i<4;i++) {
			if(x + dx[i] < n && y + dy[i] < n && x+dx[i] > -1 && y + dy[i] > -1) {
				if(ocean[x+dx[i]][y+dy[i]] == size || ocean[x+dx[i]][y+dy[i]] == 0 && visit[x+dx[i]][y+dy[i]]==-1) {
					visit[x+dx[i]][y+dy[i]] = 1;
					
					movequ.add(new Point(x+dx[i],y+dy[i],distance));
					
					//System.out.println("x : "+ (x+dx[i])+ " y : "+ (y+dy[i])+ " distance : "+ distance);
				}else if(ocean[x+dx[i]][y+dy[i]] > 0 &&ocean[x+dx[i]][y+dy[i]] < size && visit[x+dx[i]][y+dy[i]]==-1) {
					visit[x+dx[i]][y+dy[i]] = 1;
					
					if(eatqu.size()<1) {
						movequ.add(new Point(x+dx[i],y+dy[i],distance));
						eatqu.add(new Point(x+dx[i],y+dy[i],distance));
					//	System.out.println("<2 eat x : "+ (x+dx[i])+ " y : "+ (y+dy[i])+ " distance : "+ distance);
					}else {
						if(eatqu.peek().distance == distance) {
							//movequ.add(new Point(x+dx[i],y+dy[i],distance));
							eatqu.add(new Point(x+dx[i],y+dy[i],distance));
							//return;
						//	System.out.println("== eat x : "+ (x+dx[i])+ " y : "+ (y+dy[i])+ " distance : "+ distance);
						}else {
							movequ.removeAll(movequ);
							return;
						}
						
					}
					
				}
			}
		}
	}
	public static void init() {
		for(int i =0; i<n;i++) {
			Arrays.fill(visit[i],-1);
		}
	}
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		ocean  = new int[n][n];
		visit = new int[n][n];
	
		for(int i =0; i<n;i++) {
			for(int j=0; j<n;j++) {
				ocean[i][j] = sc.nextInt();
				if(ocean[i][j] == 9) {
					sharkqu.add(new Shark(i,j,2,0,0));
				}
			}
		}
		
		init();
		
		sc.close();

		int result =0;
		while(!sharkqu.isEmpty()) {
			Shark shark =sharkqu.poll();
			int sharkX =shark.sharkX;
			int sharkY = shark.sharkY;
			int sharkSize = shark.sharkSize;
			int eat = shark.eat;
			int distance = shark.distance;
			result =distance;
			ocean[sharkX][sharkY] = 9;
			
			movequ.add(new Point(sharkX,sharkY,distance));
			visit[sharkX][sharkY] =1;
			while(!movequ.isEmpty()) {
				
				Point point=movequ.poll();
				visit[point.x][point.y]=1;
				//if(movequ.size()>0)
				bfs(point.x, point.y,sharkSize,point.distance);
				
				
			}
			//Point[]  p= new Point[eatqu.size()];
		//	movequ.removeAll(movequ);
			
			int d =Integer.MAX_VALUE;
			int x =Integer.MAX_VALUE;
			int y =Integer.MAX_VALUE;
			
			if(eatqu.size() > 0) {
				while(!eatqu.isEmpty()){
						Point point = eatqu.poll();
					//	System.out.println("point x : "+point.x + " point y : "+point.y);
						if(d > point.distance) {
							d = point.distance;
							x=point.x;
							y = point.y;
							
						}else if(d == point.distance) {
							if(point.x < x) {
								x=point.x;
								y = point.y;
								d = point.distance;
								
							}else if(point.x == x){
								if(point.y < y) {
									x=point.x;
									y = point.y;
									d=point.distance;
								}
							}
						}
					//	System.out.println("the last x : "+ x + " y : " + y + " distance : "+d);
						//p[i] =point;
					}
				//	System.out.println("eat : "+ eat);
					eat++;
					
					if(sharkSize == eat) {
						++sharkSize;
						ocean[sharkX][sharkY] =0;
						sharkqu.add(new Shark(x,y,sharkSize,0,d));
						
					}else {
						
						ocean[sharkX][sharkY] =0;
						sharkqu.add(new Shark(x,y,sharkSize,eat,d));
						
					}
					
			}
			init();

		
		}
		System.out.println(result);
		
		
	}

}
class Point{
	int x;
	int y;
	int distance;
	public Point(int x, int y,int distance) {
		this.x = x;
		this.y = y;
		this.distance = distance;
	}
}

class Shark{
	int sharkX;
	int sharkY;
	int sharkSize;
	int eat;
	int distance;
	
	
	public Shark(int sharkX, int sharkY, int sharkSize, int eat, int distance) {
		this.sharkX = sharkX;
		this.sharkY = sharkY;
		this.sharkSize = sharkSize;
		this.eat = eat;
		this.distance = distance;
		
		
	}
	
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

아기상어 시간초과가 납니다.

jakyung8 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
