글 읽기 - 2178 미로탐색 메모리초

jun2077681 7년 전 0

저 코드대로 했는데 메모리 초과 뜨네요... 어떻게 해결해야하나요??ㅠㅠ

#include <stdio.h>

struct queueNode {
	int data1;
	int data2;
	int data3;
	struct queueNode *nextPtr;
};



typedef struct queueNode QueueNode;
typedef QueueNode *QueueNodePtr;
void enqueue(QueueNodePtr *headPtr, QueueNodePtr *tailPtr, int x, int y, int l);
void dequeue(QueueNodePtr *headPtr, QueueNodePtr *tailPtr);
int isEmpty(QueueNodePtr headPtr);

int m, n, count = 0;
int map[101][101];
QueueNodePtr headPtr = NULL;
QueueNodePtr tailPtr = NULL;

void BFS(int x, int y)
{
	int pos = 0;
	int tempx, tempy, templ;
	enqueue(&headPtr, &tailPtr, x, y, 1);
	while (pos < count && ((tailPtr->data1 != n - 1) || (tailPtr->data2 != m - 1)))
	{
		map[headPtr->data1][headPtr->data2] = 0;
		tempx = headPtr->data1;
		tempy = headPtr->data2;
		templ = headPtr->data3;
		if (tempy > 0 && map[tempx][tempy - 1] == 1)
			enqueue(&headPtr, &tailPtr, tempx, tempy - 1, templ + 1);
		if (tempy < m - 1 && map[tempx][tempy + 1] == 1)
			enqueue(&headPtr, &tailPtr, tempx, tempy + 1, templ + 1);
		if (tempx > 0 && map[tempx - 1][tempy] == 1)
			enqueue(&headPtr, &tailPtr, tempx - 1, tempy, templ + 1);
		if (tempx < n - 1 && map[tempx + 1][tempy] == 1)
			enqueue(&headPtr, &tailPtr, tempx + 1, tempy, templ + 1);

		pos++;
		dequeue(&headPtr, &tailPtr);
	}
	if (pos < count)
		printf("%d", tailPtr->data3);
}

int main(void)
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%1d", &map[i][j]);
	BFS(0, 0);
	return 0;
}

void enqueue(QueueNodePtr *headPtr, QueueNodePtr *tailPtr, int x, int y, int l)
{
	QueueNodePtr newPtr;
	count++;
	newPtr = malloc(sizeof(QueueNode));

	if (newPtr != NULL)
	{
		newPtr->data1 = x;
		newPtr->data2 = y;
		newPtr->data3 = l;
		newPtr->nextPtr = NULL;
		if (isEmpty(*headPtr))
		{
			*headPtr = newPtr;
		}
		else
		{
			(*tailPtr)->nextPtr = newPtr;
		}
		*tailPtr = newPtr;
	}
	else
	{
		return -1;
	}
}
void dequeue(QueueNodePtr *headPtr, QueueNodePtr *tailPtr)
{
	int value1, value2, value3;
	QueueNodePtr tempPtr;
	value1 = (*headPtr)->data1;
	value2 = (*headPtr)->data2;
	value3 = (*headPtr)->data3;
	tempPtr = *headPtr;
	*headPtr = (*headPtr)->nextPtr;
	if (*headPtr == NULL)
		*tailPtr = NULL;
	free(tempPtr);
}

int isEmpty(QueueNodePtr headPtr)
{
	return headPtr == NULL;
}

gallopsys 7년 전 1

28번 줄 while에 방문할 때마다 map[headPtr->data1][headPtr->data2] = 0;를 해서 visited를 체크하게 되면 중복으로 탐색하는 경우가 기하급수적으로 늘어나게 됩니다.

따라서 enqueue를 해주실 때, map의 해당좌표를 0으로 만들어 또 enqueue가 되지 않도록 만들어주셔야 합니다.

jun2077681 7년 전 0

감사합니다 ㅠ.ㅠ

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

문제

문제

출처

ICPC

2178 미로탐색 메모리초

jun2077681 7년 전 0

gallopsys 7년 전 1

jun2077681 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말