글 읽기 - BFS 3055번 메모리 초과 질문 드립니다.

chunseunghun 3년 전 0

이런식으로 작성을 하였는데,메모리 초과가 계속나서 질문드립니다.전역변수가 너무 많아서 그런것인지 아니면 BFS 알고리즘이 효율적이지 않아서 그런 것인지 궁금합니다.BFS 알고리즘은 먼저 물이 있는 지역들에서 사방으로 한칸씩 퍼트리고 그다음 고슴도치가 S지점에서 시작해서 사방으로 한칸씩 움직이는 방식으로 하여(고슴도치의 발자국은 G로 하였습니다.) 마지막 D 지점에 도착했을때 움직인 발걸음(ans 변수)을 출력하도록 짰는데,무엇이 메모리 초과의 원인인지 궁금합니다.일단,문제에 주어진 케이스 모두 답이 일치합니다.

package algorithm_test;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

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

public class BackJoon_BFS_3055 {
	private static int m;  //가로의 크기
	private static int n;  //세로의 크기
	private static String[][] v; //맵
	private static int[] dx = {-1,0,1,0};
	private static int[] dy = {0,-1,0,1};
	private static pairs dest; //도착 좌표
	private static pairs start; //시작 좌표
	private static pairs[] hongsu; //물의 위치 좌표들
	private static Queue<pairs> s = new LinkedList<pairs>(); //고슴도치 위치 큐
	private static Queue<pairs> h = new LinkedList<pairs>(); //물의 위치 큐
	private static int ans; // 고슴도치의 발자국 걸음 수
	
	public static String bfs(pairs start) {
		s.add(start);
		for(int i = 0;i < hongsu.length;i++) {
			if(hongsu[i] == null)
				break;
			h.add(hongsu[i]);
		}

		while(!s.isEmpty()) {
			if(v[dest.y][dest.x].equals("G"))
				break;
			
			for(int i = 0;i < h.size();i++) {
				pairs t = h.remove();
				for(int j = 0; j < dx.length;j++) {
					int nx = t.x + dx[j];
					int ny = t.y + dy[j];
					if(nx >= 0 && nx < m && ny >= 0 && ny < n && !v[ny][nx].equals("S") && 
							!v[ny][nx].equals("D") && !v[ny][nx].equals("X") && !v[ny][nx].equals("*")) {
						v[ny][nx] = "*";
						h.add(new pairs(nx,ny));
					}
				}
			}
			
			for(int i = 0;i < s.size();i++) {
				pairs t = s.remove();
				for(int j = 0;j < dx.length;j++) {
					int nx = t.x + dx[j];
					int ny = t.y + dy[j];
					if(nx >= 0 && nx < m && ny >= 0 && ny < n && !v[ny][nx].equals("X") && 
							!v[ny][nx].equals("*") && !v[ny][nx].equals("S")) {
						v[ny][nx] = "G";
						s.add(new pairs(nx,ny));
					}
				}
			}
			ans++;
		}
		
		if(v[dest.y][dest.x].equals("G"))
			return String.valueOf(ans);
		else
			return "KAKTUS";
	}
	
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		n = stdIn.nextInt();
		m = stdIn.nextInt();
		v = new String[n][m];
		int hongsui = 0;
		hongsu = new pairs[n * m];
		
		for(int i = 0;i < n;i++) {
			String str = stdIn.next();
			for(int j = 0;j < m;j++) {
				if(str.substring(j,j + 1).equals("D")) {
					dest = new pairs(j,i);
				} else if(str.substring(j,j + 1).equals("S")) {
					start = new pairs(j,i);
				} else if(str.substring(j,j + 1).equals("*")) {
					hongsu[hongsui++] = new pairs(j,i);
				}
					v[i][j] = str.substring(j,j + 1);
			}
		}
		System.out.println(bfs(start));
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

BFS 3055번 메모리 초과 질문 드립니다.

chunseunghun 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말