글 읽기 - 메모리 초과 질문.

uss425 3년 전 0

BFS를 조금 수정해서 코드를 짜봤습니다.

메모리 초과가 어디서 나는지 잘 모르겠어서 질문글 올려봅니다.. 도와주세요 ㅜㅜ

#include <iostream>
#include <queue>
using namespace std;

struct pos { int z; int y; int x; int val; };

pos s, f; //start, finish pos

const int dy[6]={0,0,1,-1,0,0};
const int dx[6]={0,0,0,0,1,-1};
const int dz[6]={1,-1,0,0,0,0};

int building[31][31][31]; //minute 연산 
int l, r, c;

void BFS(int z, int y, int x)
{
	queue<pos> q;
	q.push({z, y, x, 0});
		
	while(!q.empty())
	{
		pos curr = q.front();
		q.pop();
		
		building[curr.z][curr.y][curr.x] = curr.val;
		
		for(int i=0; i<6; i++)
		{
			pos next = {curr.z+dz[i], curr.y+dy[i], curr.x+dx[i], curr.val+1};
			
			if(next.z<0 || next.y<0 || next.x<0 
				|| next.z>=l || next.y>=r || next.x>=c) continue;
			if(building[next.z][next.y][next.x]!=0) continue;
			
			q.push(next);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	while(1)
	{
		char input;
			
		cin>>l>>r>>c;
		if(!(l || r || c)) break;
		
		for(int k=0; k<l; k++)
		for(int i=0; i<r; i++)
		for(int j=0; j<c; j++)
		{
			cin>>input;
		
			switch (input)
			{
			case 'S': //시작 좌표 저장  
				s = {k, i, j};
				break;
			case 'E': //끝 좌표 저장 
				f = {k, i, j};
				break;
			case '.': //빈칸일 경우 0 
				building[k][i][j]=0;
				break;
			case '#': //벽이면 -1 저장  
				building[k][i][j]=-1;
				break;
			}
		}
		
		BFS(s.z, s.y, s.x);
		
		if(building[f.z][f.y][f.x]==0) 
			cout<<"Trapped!\n";
		else
			cout<<"Escaped in "<<building[f.z][f.y][f.x]<<" minute(s).\n";
		
		//clear data
		for(int k=0; k<l; k++)
		for(int i=0; i<r; i++)
		for(int j=0; j<c; j++)
			building[k][i][j]=0;
	}
	
	return 0;
}

rnjstpgns91 3년 전 1

큐에 넣고 차례가 왔을 때 체크를하면 중복이 많이 발생합니다.

oxo o -> x로 이동하는 모습일 때 x에서 방문 체크를 하게되면 이미 x에는 상하좌우 4군데에서 큐에 넣은 상태입니다.

uss425 3년 전 0

방문 체크를 if(building[next.z][next.y][next.x]!=0) continue; 요렇게 하려고 했었는데,

bool 형 visited 배열로 다시 하니까 되네요.

#include <iostream>
#include <queue>
using namespace std;

struct pos { int z; int y; int x; int val; };

pos s, f; //start, finish pos

const int dy[6]={0,0,1,-1,0,0};
const int dx[6]={0,0,0,0,1,-1};
const int dz[6]={1,-1,0,0,0,0};

int building[31][31][31]; //minute 연산 
bool visited[31][31][31];
int l, r, c;

void BFS(int z, int y, int x)
{
	queue<pos> q;
	q.push({z, y, x, 0});
	visited[z][y][x] = true;
	
	while(!q.empty())
	{
		pos curr = q.front();
		q.pop();
		
		building[curr.z][curr.y][curr.x] = curr.val;
		
		if(curr.z == f.z && curr.y == f.y && curr.x == f.x) return;
		
		for(int i=0; i<6; i++)
		{
			pos next = {curr.z+dz[i], curr.y+dy[i], curr.x+dx[i], curr.val+1};
			
			if(next.z<0 || next.y<0 || next.x<0 
				|| next.z>=l || next.y>=r || next.x>=c) continue;
			if(building[next.z][next.y][next.x]==-1) continue;
			if(visited[next.z][next.y][next.x]) continue;
			
			q.push(next);
			visited[next.z][next.y][next.x]=true;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	while(1)
	{
		char input;
			
		cin>>l>>r>>c;
		if(!(l || r || c)) break;
		
		for(int k=0; k<l; k++)
		for(int i=0; i<r; i++)
		for(int j=0; j<c; j++)
		{
			cin>>input;
		
			switch (input)
			{
			case 'S': //시작 좌표 저장  
				s = {k, i, j};
				break;
			case 'E': //끝 좌표 저장 
				f = {k, i, j};
				break;
			case '.': //빈칸일 경우 0 
				building[k][i][j]=0;
				break;
			case '#': //벽이면 -1 저장  
				building[k][i][j]=-1;
				break;
			}
		}
		
		BFS(s.z, s.y, s.x);
		
		if(building[f.z][f.y][f.x]==0) 
			cout<<"Trapped!\n";
		else
			cout<<"Escaped in "<<building[f.z][f.y][f.x]<<" minute(s).\n";
		
		//clear data
		for(int k=0; k<l; k++)
		for(int i=0; i<r; i++)
		for(int j=0; j<c; j++)
		{
			building[k][i][j]=0;
			visited[k][i][j]=false;
		}
	}
	
	return 0;
}

uss425 3년 전 0

building 배열을 push 할때 체크해주니까, visited 없이도 해결 했습니다. :) 감사합니다.

#include <iostream>
#include <queue>
using namespace std;

struct pos { int z; int y; int x; int val; };

pos s, f; //start, finish pos

const int dy[6]={0,0,1,-1,0,0};
const int dx[6]={0,0,0,0,1,-1};
const int dz[6]={1,-1,0,0,0,0};

int building[31][31][31]; //minute 연산 
int l, r, c;

void BFS(int z, int y, int x)
{
	queue<pos> q;
	q.push({z, y, x, 0});
	building[z][y][x]=0;
	
	while(!q.empty())
	{
		pos curr = q.front();
		q.pop();
		
		if(curr.z == f.z && curr.y == f.y && curr.x == f.x) return;
		
		for(int i=0; i<6; i++)
		{
			pos next = {curr.z+dz[i], curr.y+dy[i], curr.x+dx[i], curr.val+1};
			
			if(next.z<0 || next.y<0 || next.x<0 
				|| next.z>=l || next.y>=r || next.x>=c) continue;
			if(building[next.z][next.y][next.x]!=0) continue; //방문했을 경우 or 벽 
			
			q.push(next);
			building[next.z][next.y][next.x] = next.val;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	while(1)
	{
		char input;
			
		cin>>l>>r>>c;
		if(!(l || r || c)) break;
		
		for(int k=0; k<l; k++)
		for(int i=0; i<r; i++)
		for(int j=0; j<c; j++)
		{
			cin>>input;
		
			switch (input)
			{
			case 'S': //시작 좌표 저장  
				s = {k, i, j};
				break;
			case 'E': //끝 좌표 저장 
				f = {k, i, j};
				break;
			case '.': //빈칸일 경우 0 
				building[k][i][j]=0;
				break;
			case '#': //벽이면 -1 저장  
				building[k][i][j]=-1;
				break;
			}
		}
		
		BFS(s.z, s.y, s.x);
		
		if(building[f.z][f.y][f.x]==0) 
			cout<<"Trapped!\n";
		else
			cout<<"Escaped in "<<building[f.z][f.y][f.x]<<" minute(s).\n";
		
		//clear data
		for(int k=0; k<l; k++)
		for(int i=0; i<r; i++)
		for(int j=0; j<c; j++)
			building[k][i][j]=0;
	}
	
	return 0;
}

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

문제

문제

출처

ICPC

메모리 초과 질문.

uss425 3년 전 0

rnjstpgns91 3년 전 1

uss425 3년 전 0

uss425 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말