글 읽기 - bfs 메모리 초과

guftkcldh 3년 전 0

dfs 방식에서 bfs 방식으로 변경했는데도 메모리 초과가 납니다.

bfs 함수에서 if 안에 어떤 조건을 추가해야 메모리 초과가 발생하지 않을까요??

고수님들 조언 부탁드립니다.

#include<stdio.h>
#include<iostream>
#include<queue>

using namespace std;

class node
{
public:
	int a,b;	
};

int m,n;
int p[2][2];
char arr[102][102];
int check[102][102][3];

void bfs(int x, int y, int c)
{
	queue<node> q;
	int i,j;
	
	q.push({x,y});
	check[x][y][c]=0;
	
	while(!q.empty())
	{
		i=q.front().a;
		j=q.front().b;
		
		if(i-1>=0 && check[i-1][j][c]>check[i][j][c] && arr[i-1][j]!='*')
		{
			if(arr[i-1][j]=='#')
			{
				check[i-1][j][c] = check[i][j][c]+1;
				q.push({i-1,j});
			}
			
			else
			{
				check[i-1][j][c] = check[i][j][c];
				q.push({i-1,j});				
			}
		} 
		
		if(j-1>=0 && check[i][j-1][c]>check[i][j][c] && arr[i][j-1]!='*')
		{
			if(arr[i][j-1]=='#')
			{
				check[i][j-1][c] = check[i][j][c]+1;
				q.push({i,j-1});
			}
			
			else
			{
				check[i][j-1][c] = check[i][j][c];
				q.push({i,j-1});				
			}
		} 
		
		if(i+1<=m+1 && check[i+1][j][c]>check[i][j][c] && arr[i+1][j]!='*')
		{
			if(arr[i+1][j]=='#')
			{
				check[i+1][j][c] = check[i][j][c]+1;
				q.push({i+1,j});
			}
			
			else
			{
				check[i+1][j][c] = check[i][j][c];
				q.push({i+1,j});				
			}
		} 
		
		if(j+1<=n+1 && check[i][j+1][c]>check[i][j][c] && arr[i][j+1]!='*')
		{
			if(arr[i][j+1]=='#')
			{
				check[i][j+1][c] = check[i][j][c]+1;
				q.push({i,j+1});
			}
			
			else
			{
				check[i][j+1][c] = check[i][j][c];
				q.push({i,j+1});				
			}
		} 	
		
		q.pop();					
	}
}

int main()
{
	int test,t,i,j,k,min;
	
	scanf("%d",&test);
	
	for(t=0;t<test;t++)
	{
		scanf("%d%d",&m,&n);
		getchar();
		k=0;
		
		for(i=0;i<102;i++)
		{
			for(j=0;j<102;j++)
			{
				arr[i][j]='.';
				check[i][j][0]=101*101;
				check[i][j][1]=101*101;
				check[i][j][2]=101*101;
			}
		}	
		
		for(i=1;i<m+1;i++)
		{
			for(j=1;j<n+1;j++)
			{
				scanf("%c",&arr[i][j]);
				if(arr[i][j]=='$')
				{
					p[k][0]=i;
					p[k][1]=j;
					k++;
				}
			}
			getchar();
		}
		bfs(0,0,0);
		bfs(p[0][0],p[0][1],1);
		bfs(p[1][0],p[1][1],2);
		
	/*	for(i=0;i<m+2;i++)
		{
			for(j=0;j<n+2;j++)
			{
				printf("%6d ",check[i][j][0]);
			}
			printf("\n");
		}
		printf("\n");
		
		for(i=0;i<m+2;i++)
		{
			for(j=0;j<n+2;j++)
			{
				printf("%6d ",check[i][j][1]);
			}
			printf("\n");
		}
		printf("\n");		
		
		for(i=0;i<m+2;i++)
		{
			for(j=0;j<n+2;j++)
			{
				printf("%6d ",check[i][j][2]);
			}
			printf("\n");
		}
		printf("\n");*/
		
		min=999999;
		for(i=0;i<m+2;i++)
		{
			for(j=0;j<n+2;j++)
			{
				if(arr[i][j]=='#')
				{
					check[i][j][0]=check[i][j][0]-2;
				}
			}
		}
		
		for(i=0;i<m+2;i++)
		{
			for(j=0;j<n+2;j++)
			{
				if(check[i][j][0]+check[i][j][1]+check[i][j][2]<min)
				{
					min=check[i][j][0]+check[i][j][1]+check[i][j][2];
				}
			}
		}
		printf("%d\n",min);			
	}
	
	return 0;
}

palilo 3년 전 0

0-1 BFS 문제입니다 한 번 검색해보세요

이게 왜 메모리 초과가 나냐면 맵이 아래처럼 생겼을 때,

죄수가 왼쪽으로 이동하면서 왼쪽 부근의 check[][] 값을 다 1로 만들겁니다.

하지만 위, 아래로 갔다가 왼쪽으로 가면 check[][]값이 0이 되기 때문에 다시 큐에 넣는 작업을 할겁니다.

왼쪽 부근의 맵을 두 번 계산하게 되죠

맵이 훨씬 복잡해지면 같은 장소를 수 십번 방문할 수 있고, 큐에 너무 많은 데이터가 담겨서 터집니다.

.......
.......
..#$...
.......
.......

guftkcldh 3년 전 0

그러면 .과 #이 있을 경우에는 .을 먼저 방문한다는 조건을 달아주면 해결 가능하겠군요..

소중한 댓글 감사드립니다. 좋은 하루 되세요.

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

문제

문제

출처

ICPC

bfs 메모리 초과

guftkcldh 3년 전 0

palilo 3년 전 0

guftkcldh 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말