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

neogate 2년 전 0

경우의 수도 줄여보고 queue의 크기도 줄여봤는데 메모리초과가 바랭합니다.

더 줄일수 있는 방법이 있을까요....?

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <queue>
#define INF 987654321
using namespace std;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int main() {
	int n,m;
	cin>>n>>m;
	char map[52][52]={0};
	memset(map,'#',sizeof(map));
	int sx,sy;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>map[i][j];
			if(map[i][j]=='0'){
				sx=i; sy=j;
			}
		}
	}
	queue<pair<pair<pair<char,char>,pair<char,char>>,pair<char,char>>>q; // x, y, time, key(bitmask)
	q.push({{{sx,sy},{0,0}},{0,0}});
	int ans=INF;
	int prex=0,prey=0;
	while(!q.empty()){
		auto i=q.front(); q.pop();
		int x=i.first.first.first,y=i.first.first.second,time=i.second.first,key=i.second.second,cdx=i.first.second.first,cdy=i.first.second.second;
		int flag=0;
		if(map[x][y]=='1'){
			ans=time;
			break;
		}
		else if(map[x][y]>='a'&&map[x][y]<='f'){
			if((key&(1<<(map[x][y]-'a')))==0){
				key=key|(1<<(map[x][y]-'a'));
			}
			else flag=1;
		}
		else if(map[x][y]>='A'&&map[x][y]<='F'){
			if((key&(1<<(map[x][y]-'A')))==0) flag=1;
		}
		if(flag) continue;
		for(int i=0;i<4;i++){
			if(map[x+dx[i]][y+dy[i]]!='#'){
				if((!(map[x][y]>='a'&&map[x][y]<='f')&&(dx[i]*cdx==-1||dy[i]*cdy==-1))) continue;
				else q.push({{{x+dx[i],y+dy[i]},{dx[i],dy[i]}},{time+1,key}});
			}
		}
	}
	if(ans==INF) cout<<-1<<endl;
	else cout<<ans<<endl;
}

djm03178 2년 전 1

BFS를 할 때 메모리 초과가 나면 원인은 99% 제대로 방문 체크를 안 했기 때문입니다. 이 코드도 방문 체크를 하고 있지 않아 중복된 정점이 큐에 반복적으로 쌓이면서 지수 복잡도의 시공간을 요구하게 됩니다.

neogate 2년 전 0

아 방문 체크 과정에서 비트마스킹을 활용하면 쉬운 문제였네요ㅠ 감사합니다!

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

문제

문제

출처

ICPC

메모리초과 질문입니다.

neogate 2년 전 0

djm03178 2년 전 1

neogate 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말