글 읽기 - BFS로 풀었을때 메모리초과 질문드립니다!

kwpark96 4년 전 0

20 20
POIUYTREWQBWKALSLDLG
LKJHGFDSAMASFBMBOSOZ
NMBVCXZAKPAISJLBMROW
CEVTBFNIMLASNCVKNDKX
VPQLBKENMSAHBBLFOWPQ
ZLSKJJBNBEASZNFDGHHN
GPBMDLQDALAASBBXCEGA
APQIKBMROIBANPOBLMKS
ASKSKVJRPORHNOXZKSPN
LSNVOEOOOKAKANLGKOAX
AKVMBOTOWPQOJBSMSPEP
BLLBKWPEPBKNMROSALLP
BNQLDNBMKOVMEMELSLMA
RLEPQQPVKJRNBITNBSAS
ZXMCOITRPWKLPGKHNGMS
QOBKRPPPZSLEMPNKSPPR
OQJDNZNANDWKQKVJEOGJ
QUYVOIUYWERLKJHASDFV
ZCVWRETPOIUHJKLVBMAS
QWERZCVUIAFDKHSDFHSA

-> 26

이 코드도 컴파일러(dev)상에서는 잘돌아가는데

제출하면 메모리초과가 뜨는데 왜그런가요..? 20*20이라 메모리초과 뜰 것도 없을것같은데..

#include <stdio.h>
#include <queue>
using namespace std;

typedef struct node
{
	int x;
	int y;
	int key;
	int cnt;
}node;

char map[20][20];
int row, col;
int Max;

int dx[4] = {-1, 1, 0, 0}; // 상하좌우 
int dy[4] = {0, 0, -1, 1}; // 상하좌우

queue<node> q;

int safe(int x, int y)
{
	if(x >= 0 && y >= 0 && x < row && y < col)
	{
		return 1;
	}
	else
	{
		return 0;
	}
} 

void BFS(int x, int y)
{
	int key = 1 << (map[x][y]-'A');
	int cnt = 1;
	
	q.push({x, y, key, cnt});
	
	while(!q.empty())
	{
		x = q.front().x;
		y = q.front().y;
		key = q.front().key;
		cnt = q.front().cnt;
		q.pop();
		
		if(cnt > Max)
		{
			Max = cnt;
		}
		
		for(int i = 0; i < 4; i++)
		{
			int xpos = x+dx[i];
			int ypos = y+dy[i];
			
			if(safe(xpos, ypos) == 1)
			{
				int keypos = key | (1 << (map[xpos][ypos]-'A'));
			
				if(keypos != key)
				{
					q.push({xpos, ypos, keypos, cnt+1});
				}	
			}
		}
	}
}

int main(void)
{
	// freopen("B1987_input.txt", "r", stdin);
	
	scanf("%d %d", &row, &col);
	
	for(int i = 0; i < row; i++)
	{
		for(int j = 0; j < col; j++)
		{
			scanf(" %c", &map[i][j]);
		}
	}
	
	BFS(0, 0);
	
	printf("%d", Max);
		
	return 0;
}

sait2000 4년 전 0

이러면 어떨까요. 큐 크기가 몇까지 올라가나 알아보시면 왜 메모리 초과가 나는지 아실 거라고 생각합니다.

in:
20 20
ABCDEFGHIJKLMNOPQRST
BCDEFGHIJKLMNOPQRSTU
CDEFGHIJKLMNOPQRSTUV
DEFGHIJKLMNOPQRSTUVW
EFGHIJKLMNOPQRSTUVWX
FGHIJKLMNOPQRSTUVWXY
GHIJKLMNOPQRSTUVWXYZ
HIJKLMNOPQRSTUVWXYZA
IJKLMNOPQRSTUVWXYZAB
JKLMNOPQRSTUVWXYZABC
KLMNOPQRSTUVWXYZABCD
LMNOPQRSTUVWXYZABCDE
MNOPQRSTUVWXYZABCDEF
NOPQRSTUVWXYZABCDEFG
OPQRSTUVWXYZABCDEFGH
PQRSTUVWXYZABCDEFGHI
QRSTUVWXYZABCDEFGHIJ
RSTUVWXYZABCDEFGHIJK
STUVWXYZABCDEFGHIJKL
TUVWXYZABCDEFGHIJKLM

out:
26

kwpark96 4년 전 0

이 문제는 BFS로 풀엇을때 좌표로 방문체크를 못하기떄문에 메모리초과생겨서 DFS로 풀어야하는것인가요>??

sait2000 4년 전 0

저 애초에 BFS로 풀었는데요. 그냥 거리가 같은 지점을 다 돌아본 다음에 중복되는 지점을 없에면 돼요. DFS로 푼다는 생각은 못했어요.

vector<T> s;

int main() {
    scanf("...", ...);
    for (...) {
        scanf("...", ...);

    s.push_back({...}); // initialize s
    int gen = 0;
    for ( ; !s.empty(); ++gen) {
        vector<T> olds;
        swap(s, olds);
        olds.erase(unique(olds.begin(), olds.end()), olds.end());

        // visit next
        for (auto& pr : olds) {
            ...
        }
    }
    printf("%d\n", gen);
}

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

문제

문제

출처

ICPC

BFS로 풀었을때 메모리초과 질문드립니다!

kwpark96 4년 전 0

sait2000 4년 전 0

kwpark96 4년 전 0

sait2000 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말