글 읽기 - 미로찾기 :런타임에러가 나는데 이유를 모르겠습니다

boffin 6년 전 0

잘 돌아가는데 제출해보면 런타임에러가 뜨네요

왜 그럴까요..?ㅠ

#include<stdio.h>

typedef struct lastxy
{
	int x;
	int y;
}lastxy;


int main() {
	int N, M;
	int maz[101][101] = { 0 };
	_Bool che[101][101] = { 0 };
	int dp[101][101] = { 0 };
	lastxy que[10001] = { 0 };
	int nextx[4] = { 1,-1,0,0 };
	int nexty[4] = { 0,0,1,-1 };
	lastxy next,cur;
	int front=1, tail=1;

	scanf("%d %d", &N, &M);



	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			scanf("%1d", &maz[i][j]);

	cur.x = 1;
	cur.y = 1;

	que[front].x = 1;
	que[front].y = 1;

	dp[1][1] = 1;


	while (front<=tail) {
		for (int i = 0; i < 4; i++) {
			next.x = cur.x + nextx[i];
			next.y = cur.y + nexty[i];

			if(che[next.y][next.x]==0&&next.x>0 && next.x<=M && next.y>0 && next.y<=N)
				if (maz[next.y][next.x] == 1) {
					dp[next.y][next.x] = dp[cur.y][cur.x] + 1;
					que[++tail] = next;
				}
		}
		che[cur.y][cur.x] = 1;
		cur = que[++front];
	}

	printf("%d", dp[N][M]);
}

djm03178 6년 전 1

che에 값을 나중에 대입해서 그렇습니다. 가령, 2x2 맵의 모든 칸이 이동할 수 있는 칸이면 che가

0 0

과 같은 상태에서 출발하고, 한 번 루프를 돌면

1 0

0 0

이 되어 있을 것이고, 그 다음은

1 1

0 0

이 될텐데, 이 때 이미 (2, 2) 좌표는 큐에 들어간 상황입니다. 그러나, 그 다음 루프에서는 (2, 1) 좌표를 검사하게 되고, 여전히 che[2][2]는 0이기 때문에 (2, 2)가 큐에 또 추가됩니다. 즉, 같은 좌표를 중복해서 방문하는 일이 발생합니다.

좌표의 수가 최대 10000개이고 큐의 크기도 10001인데, 큐에 중복해서 들어가는 좌표가 여럿 생기면 결국은 큐의 크기를 초과하게 될 수 있습니다. 그래서 BFS를 할 때는, 큐에 추가하는 순간에 그 좌표의 방문을 먼저 기록해두는 것이 좋습니다.

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

문제

문제

출처

ICPC

미로찾기 :런타임에러가 나는데 이유를 모르겠습니다

boffin 6년 전 0

djm03178 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말