글 읽기 - 정답을 맞추기는 했는데 궁금한 점이 있습니다

sm1108shin 2년 전 0

큐에 들어갈 최대 가짓수가 1001*1001*2라고 생각해서 큐의 크기를 해당 크기만큼 할당하니 런타임에러(accessnullpointer)가 발생합니다

그래서 그것보단 좀더 넉넉하게 크기를 대충 2500000으로 할당해주니까 돌아가네요

1001*1001*2로 할당하면 왜 런타임에러가 발생하는지 궁금합니다

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_SIZE 2500000

typedef struct _queue
{
	int x;
	int y;
	int cnt;
	int op;
}Queue;

int f = -1;
int r = -1;
char arr[1001][1001];
int visited[1001][1001][2];//인덱스 0은 벽을 깨지 않은 경로, 인덱스 1은 벽을 깬 경로
Queue* Queuearr[MAX_SIZE];

int is_empty()
{
	if (f == r)
	{
		return 1;
	}
	return 0;
}

void enqueue(Queue* q[], int i, int j, int cnt, int op)
{
	if (visited[i][j][op])//중복 검사
	{
		return;
	}
	if (r == MAX_SIZE)
	{
		exit(0);
	}
	r++;
	q[r]->x = i;
	q[r]->y = j;
	q[r]->cnt = cnt;
	q[r]->op = op;
}

Queue* dequeue(Queue* q[])
{
	if (is_empty())
	{
		printf("Queue is Empty\n");
		exit(0);
	}
	f++;
	return q[f];

}

void maze(Queue* Queuearr[], int x, int y, int n, int m, int cnt, int op)
{

	if (x < 0 || x >= n || y < 0 || y >= m)
	{
		return;
	}

	if (op == 1)//이미 벽을 깬 전적이 있는 경로
	{
		if (x + 1 < n && arr[x + 1][y] == '0')
		{
			enqueue(Queuearr, x + 1, y, cnt + 1, 1);
			visited[x + 1][y][op] = 1;
		}
		if (x - 1 >= 0 && arr[x - 1][y] == '0')
		{
			enqueue(Queuearr, x - 1, y, cnt + 1, 1);
			visited[x - 1][y][op] = 1;
		}
		if (y + 1 < m && arr[x][y + 1] == '0')
		{
			enqueue(Queuearr, x, y + 1, cnt + 1, 1);
			visited[x][y + 1][op] = 1;
		}
		if (y - 1 >= 0 && arr[x][y - 1] == '0')
		{
			enqueue(Queuearr, x, y - 1, cnt + 1, 1);
			visited[x][y - 1][op] = 1;
		}
	}
	else//아직 벽을 깬 전적이 없는 경로
	{
		if (x + 1 < n && arr[x + 1][y] == '0')
		{
			enqueue(Queuearr, x + 1, y, cnt + 1, 0);
			visited[x + 1][y][op] = 1;
		}
		if (x + 1 < n && arr[x + 1][y] == '1' && op == 0)
		{
			enqueue(Queuearr, x + 1, y, cnt + 1, 1);
			visited[x + 1][y][op] = 1;
		}

		if (x - 1 >= 0 && arr[x - 1][y] == '0')
		{
			enqueue(Queuearr, x - 1, y, cnt + 1, 0);
			visited[x - 1][y][op] = 1;
		}
		if (x - 1 >= 0 && arr[x - 1][y] == '1' && op == 0)
		{
			enqueue(Queuearr, x - 1, y, cnt + 1, 1);
			visited[x - 1][y][op] = 1;
		}

		if (y + 1 < m && arr[x][y + 1] == '0')
		{
			enqueue(Queuearr, x, y + 1, cnt + 1, 0);
			visited[x][y + 1][op] = 1;
		}
		if (y + 1 < m && arr[x][y + 1] == '1' && op == 0)
		{
			enqueue(Queuearr, x, y + 1, cnt + 1, 1);
			visited[x][y + 1][op] = 1;
		}

		if (y - 1 >= 0 && arr[x][y - 1] == '0')
		{
			enqueue(Queuearr, x, y - 1, cnt + 1, 0);
			visited[x][y - 1][op] = 1;
		}
		if (y - 1 >= 0 && arr[x][y - 1] == '1' && op == 0)
		{
			enqueue(Queuearr, x, y - 1, cnt + 1, 1);
			visited[x][y - 1][op] = 1;
		}
	}
	
}


int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < MAX_SIZE; i++)
	{
		Queuearr[i] = (Queue*)malloc(sizeof(Queue));
	}

	for (int i = 0; i < n; i++)
	{
		scanf("%s", arr[i]);
	}
	enqueue(&Queuearr, 0, 0, 1, 0);
	visited[0][0][0] = 1;
	
	int value = -1;

	while (!is_empty())
	{
		Queue* q = (Queue*)malloc(sizeof(Queue));
		q = dequeue(&Queuearr);
		//printf("%d %d %d %d\n", q->x, q->y, q->cnt, q->op);
		if (q->x == n - 1 && q->y == m - 1)
		{
			value = q->cnt;
			break;
		}
		maze(&Queuearr, q->x, q->y, n, m, q->cnt, q->op);
	}
	printf("%d", value);
}

amsminn 2년 전 0

큐에 중복원소가 들어가는 것 같네요

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

문제

문제

출처

ICPC

정답을 맞추기는 했는데 궁금한 점이 있습니다

sm1108shin 2년 전 0

amsminn 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말