글 읽기 - 런타임에러가 뜨는데 왜그런지 모르겠어요 ㅜㅜ

csheo0713 4년 전 0

런타임 에러가 떠서 배열크기도 바꾸고 해봤는데 계속 떠요 ㅜㅜ

#include <stdio.h>

int N, M;
int map[1002][1002];

typedef struct {
	int r, c, time, chance;
	// chance가 1이면 기회 한 번 사용
}Queue;
Queue queue[1001 * 1001];
int front, rear;
void enQueue(int r, int c, int time, int chance)
{
	queue[rear].r = r;
	queue[rear].c = c;
	queue[rear].time = time;
	queue[rear].chance = chance;
	rear++;
}
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };

int bfs(void)
{
	int i;
	int nr, nc;
	Queue q;
	enQueue(1, 1, 0, 0);
	map[1][1] = 2;
	while (front < rear)
	{
		q = queue[front++];
		if (q.r == N && q.c == M)
			return q.time + 1;
		for (i = 0; i < 4; i++)
		{
			nr = q.r + dr[i];
			nc = q.c + dc[i];

			if (nr<1 || nr>N || nc <1 || nc>M) continue;
			if (map[nr][nc] == 0|| map[nr][nc]==3)
			{
				enQueue(nr, nc, q.time + 1, q.chance);
				if (q.chance == 0)
					map[nr][nc] = 2;
			}
			else if (map[nr][nc] == 1)
			{
				if (q.chance == 0)
				{
					enQueue(nr, nc, q.time + 1, 1);
					map[nr][nc] = 3;
				}
			}
		}
	}
	return -1;
}
int main(void)
{
	int i, j;
	scanf("%d %d", &N, &M);
	for (i = 1; i <= N; i++)
	{
		for (j = 1; j <= M; j++)
			scanf("%1d", &map[i][j]);
	}
	printf("%d\n", bfs());

	return 0;
}

djm03178 4년 전 0

https://www.acmicpc.net/board/view/27386

csheo0713 4년 전 0

모든 칸을 전부 0으로 하나씩 바꾸어보고 BFS를 돌리는 것을 반복해서는 통과될 수 없습니다. 대부분의 알고리즘 문제가 그렇듯이, 풀이를 짜기 전에 반드시 해야 하는 것 중 하나는 시간 복잡도를 생각하는 것입니다. 시간 복잡도 계산, 전혀 어렵지 않습니다. 벽이 최대 O(NM)개 있는 맵에서, 벽을 하나 부술 때마다 O(NM)개의 칸을 탐색해야 하죠? 그러니 O((NM)^2)입니다. 이 수는 우리가 대충 1초에 돌 수 있다고 보는 단위인 1억을 10000배나 뛰어넘는 1조입니다. 절대 통과될 수 없겠죠?

이것때문인가용??

djm03178 4년 전 0

아니요, 이 코드는 그렇게 풀고 있지 않습니다. 제가 말씀드리고 싶은 것은 런타임 에러가 나는 직접적인 원인을 떠나서 이와 같이 푸는 것 자체가 올바른 해법이 아니라는 것입니다.

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

문제

문제

출처

ICPC

런타임에러가 뜨는데 왜그런지 모르겠어요 ㅜㅜ

csheo0713 4년 전 0

djm03178 4년 전 0

csheo0713 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말