글 읽기 - bfs 메모리 초과 질문입니다

yih9329 5년 전 0

메모리초과가 어떤부분에서 나는 걸까요?
할수 있는 개선은 다 한거 같은데 한번 봐주시면 감사드리겠씁니다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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


public class Main {	
	static char[][] map;
	static int[][] visit;
	static Queue<Point> pos_space;
	static Queue<Point> fire;
	static int success;
	static int w;
	static int h;
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {	
			int T = Integer.parseInt(br.readLine());
			map = new char[1000][1000];
			visit = new int[1000][1000];
			pos_space = new LinkedList<>();            // 피할 좌표를 저장하는 큐
			fire = new LinkedList<>();                // 불이 있는 좌표를 저장하는 큐
			Point start = null;
			
			while(T > 0) {
				StringTokenizer str = new StringTokenizer(br.readLine(), " ");
				w = Integer.parseInt(str.nextToken());
				h = Integer.parseInt(str.nextToken());
				success = 0;
				pos_space.clear();
				fire.clear();
				
				for(int i=0; i<h; i++) {
					String s = br.readLine();
					for(int j=0; j<w; j++) {
						map[i][j] = s.charAt(j);
						if(map[i][j] == '@')
							start = new Point(i,j);
						
						if(map[i][j] == '*')
							fire.offer(new Point(i,j));
					}
				}
				
				visit[start.x][start.y] = 1;
				pos_space.offer(start);
				escapeFire();
				if(success != 1)
					bw.write("IMPOSSIBLE\n");
				else
					bw.write(Integer.toString(getEscapeTime()) + "\n");
				
				T--;
				
				for(int i=0; i<h; i++)
					for(int j=0; j<w; j++)
						visit[i][j] = 0 ;
			}
			
			bw.flush();
			bw.close();
			br.close();
		} catch (NumberFormatException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	static void escapeFire() {
		
		while(true) {
			if(!fire.isEmpty())
				nextFire();            // 다음번에 불이 번질 구역에 '&'해둠
			
			if(!pos_space.isEmpty())
				nextSpace();            // 다음번에 갈 수 있는 좌표를 구함
			
			for(int i=0; i<h; i++){                
				for(int j=0; j<w; j++) {
					if(map[i][j] == '&')
						map[i][j] = '*';
				}
			}
			
			if(pos_space.isEmpty() || success == 1)                // 탈출구까지 왔다면 success가 1이된다. 
				break;
		}
		
	}
	
	static void nextFire() {
		
		Queue<Point> nextfire = new LinkedList<>();
			
		Point cp = fire.poll();
		
		while(true) {
			
			if(cp.x>0 && (map[cp.x-1][cp.y] == '.' || map[cp.x-1][cp.y] == '@')) {
				map[cp.x-1][cp.y] = '&';
				nextfire.offer(new Point(cp.x-1, cp.y));
			}
			
			if(cp.x<h-1 && (map[cp.x+1][cp.y] == '.' || map[cp.x+1][cp.y] == '@')) {
				map[cp.x+1][cp.y] = '&';
				nextfire.offer(new Point(cp.x+1, cp.y));
			}
			
			if(cp.y>0 && (map[cp.x][cp.y-1] == '.' || map[cp.x][cp.y-1] == '@')) {
				map[cp.x][cp.y-1] = '&';
				nextfire.offer(new Point(cp.x, cp.y-1));
			}
			
			if(cp.y<w-1 && (map[cp.x][cp.y+1] == '.' || map[cp.x][cp.y+1] == '@')) {
				map[cp.x][cp.y+1] = '&';
				nextfire.offer(new Point(cp.x, cp.y+1));
			}

			if(fire.isEmpty())
				break;
			
			cp = fire.poll();
		}
		
		fire = nextfire;
	}
	
	static void nextSpace() {
		
		Queue<Point> nextspace = new LinkedList<>();
		Point cp = pos_space.poll();
		
		while(true) {
			if(cp.x>0 && map[cp.x-1][cp.y] == '.' && visit[cp.x-1][cp.y] != 1) {
				visit[cp.x-1][cp.y] = visit[cp.x][cp.y] + 1;
				if(cp.x-1 == 0) {
					success = 1;
					return;
				}
				nextspace.offer(new Point(cp.x-1, cp.y));
			}
			
			if(cp.x<h-1 && map[cp.x+1][cp.y] == '.' && visit[cp.x+1][cp.y] != 1) {
				visit[cp.x+1][cp.y]= visit[cp.x][cp.y] + 1;
				if(cp.x+1 == h-1) {
					success = 1;
					return;
				}
				nextspace.offer(new Point(cp.x+1, cp.y));
			}
			
			if(cp.y>0 && map[cp.x][cp.y-1] == '.' && visit[cp.x][cp.y-1] != 1) {
				visit[cp.x][cp.y-1] = visit[cp.x][cp.y] + 1;
				if(cp.y-1 == 0) {
					success = 1;
					return;
				}
				nextspace.offer(new Point(cp.x, cp.y-1));
			}
			
			if(cp.y<w-1 && map[cp.x][cp.y+1] == '.' && visit[cp.x][cp.y+1] != 1) {
				visit[cp.x][cp.y+1] = visit[cp.x][cp.y] + 1;
				if(cp.y+1 == w-1) {
					success = 1;
					return;
				}
				nextspace.offer(new Point(cp.x, cp.y+1));
			}

			if(pos_space.isEmpty())
				break;
			cp = pos_space.poll();
		}
		pos_space = nextspace;
	}
	
	static int getEscapeTime() {
		int min_time = Integer.MAX_VALUE;
		
		for(int i=0; i<h; i++) {
			if(i==0 || i==h-1) {
				for(int j=0; j<w; j++) {
					if(map[i][j] == '.' && visit[i][j] != 0)
						min_time = Math.min(min_time, visit[i][j]);
					
				}
			}
			
			else {
				if(map[i][0] == '.' && visit[i][0] != 0)
					min_time = Math.min(min_time, visit[i][0]);
				
				if(map[i][w-1] == '.' && visit[i][w-1] != 0)
					min_time = Math.min(min_time, visit[i][w-1]);
			}
		}
		
		if(min_time == Integer.MAX_VALUE)
			return -1;
		else
			return min_time;
	}
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

bfs 메모리 초과 질문입니다

yih9329 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
