글 읽기 - 2178번 질문입니다.

semtax 8년 전 0

N크기가 100밖에 안되서,

인접행렬로 그래프를 나타낸 다음 BFS 를 이용해서 풀었는데 메모리 초과라고 뜨네요..

왜 안되는 걸까요? ㅎㅎ

해결 부탁드립니다 ㅠㅠ

#include <iostream>
#include <queue>

using namespace std;

#define MAX 100


typedef struct __data
{
	unsigned short x;
	unsigned short y;
	int l;
}Data;

queue<Data> Q;
char map[MAX+1][MAX+1];
int minimum;
int m,n;

void EnQueue(int x,int y,int l)
{
	Data d;
	d.x = x;
	d.y = y;
	d.l = l;
	Q.push(d);
}

Data DeQueue()
{
	Data d;
	d = Q.front();
	Q.pop();
	return d;
}

void BFS(int x, int y)
{
	if(x==1 && y==1)
    {
		EnQueue(x,y,1);
		x=-1,y=-1;
    }
	
	
	Data d;
	
	for(;;)
    {
		if(Q.empty())
        {
			break;
        }
		
		d = DeQueue();
		
		if(d.x==m && d.y==n)
        {
			minimum = d.l;
			break;
        }
		
		map[d.y][d.x] = '0';
		
		if(d.y > 1 && map[d.y-1][d.x]!='0')
        {
			EnQueue(d.x,d.y-1,d.l+1);
        }
		if(d.y < n && map[d.y+1][d.x]!='0')
        {
			EnQueue(d.x,d.y+1,d.l+1);
        }
		if(d.x > 1 && map[d.y][d.x-1]!='0')
        {
			EnQueue(d.x-1,d.y,d.l+1);
        }
		if(d.x < m && map[d.y][d.x+1]!='0')
        {
			EnQueue(d.x+1,d.y,d.l+1);
        }
			
    }
	
}

int main() {
	
	string str;
	m=0,n=0;
	cin >> n >> m;
	minimum=100000;
	
	for(int i=1;i<=n;i++)
    {
		cin >> str;
		for(int j=1;j<=m;j++)
        {
			map[i][j] = str[j-1];
        }
    }
	
	BFS(1,1);
	
	cout << minimum;
	
	return 0;
}

semtax 8년 전 0

큐에 넣을 때에만 0으로 체크 해야되는데, 조건을 잘못고려 했네요 ㅎㅎ

까먹지 않게 댓글로 남겨둡니다

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

문제

문제

출처

ICPC

2178번 질문입니다.

semtax 8년 전 0

semtax 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말