글 읽기 - 런타임오류..진짜 못 찾겠어요ㅜ,ㅠ

kjho1037 5년 전 0

좀 무식하식 하지만..

모든 벽 없애가면서 최단경로 찾아서 그 중에서 최소값 출력하는건데...

진짜 72퍼 정도에서 계속 런타임에러떠서 미치겠습니다ㅜ,ㅠ

#include <stdio.h>
#include <string.h>

#define MAX 999999

int M, N, MIN;
int MAP[1111][1111];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };


void BACK(int y, int x, int len)
{
	if (MAP[y][x] == 1 || len > MIN)
		return;

	if (y == M && x == N)
	{
		if (len < MIN)
			MIN = len;
		return;
	}

	MAP[y][x] = 1;

	for (int i = 0; i < 4; i++)
	{
		int xx = x + dx[i];
		int yy = y + dy[i];

		if (xx > N || yy > M || xx <= 0 || yy <= 0)
			continue;

		if (MAP[yy][xx] == 0)
		{
			BACK(yy, xx, len + 1);
		}

	}
	MAP[y][x] = 0;
	return;
}

int main()
{
	scanf("%d %d", &M, &N);

	for (int i = 0; i <= 1011; i++)
	{
		for (int j = 0; j <= 1011; j++)
		{
			MAP[i][j] = 1;
		}
	}

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

	MIN = MAX;

	BACK(1,1,1);//벽 부수지 않고 최단경로 찾기

	for (int i = 1; i <= M; i++)//벽 하나씩 부숴가면서 최단경로 찾기
	{
		for (int j = 1; j <= N; j++)
		{
			if (MAP[i][j] == 0 || (i == 1 && j == 1))
				continue;

			if ((MAP[i + 1][j] == 1 || i + 1 > M) &&
				(MAP[i][j + 1] == 1 || j + 1 > N) &&
				(MAP[i - 1][j] == 1 || i - 1 < 1) &&
				(MAP[i][j - 1] == 1 || j - 1 < 1))//0으로 바꾸었는데, 사방에 1이면 노 필요~
			{
				continue;
			}

			MAP[i][j] = 0;
			BACK(1, 1, 1);
			MAP[i][j] = 1;
		}
	}

	if (MIN == MAX)
	{
		printf("-1\n");
		return;
	}
	printf("%d\n", MIN);

	return 0;
}

djm03178 5년 전 1

92번째 줄을 return 0; 으로 바꿔주면 맞습니다.

그런데 이 코드가 통과되는 걸 보니 아직 데이터가 약하군요. 데이터 추가 요청을 해야겠습니다.

kjho1037 5년 전 0

답변 감사합니다.

처음에 BFS로 풀었는데...계속 시간 초과가 나더군요!!!! 생각해보니 1000*1000*1000*1000 의 시간 복잡도가 나오는 것 같은데 맞나요???

djm03178 5년 전 1

여러 가지 제약 조건 때문에 최악의 경우에도 약 1/4 정도 되긴 하지만, 기본적으로는 O(N^2*M^2)이 맞습니다.

kjho1037 5년 전 0

한 가지 궁금한게 있는데!! 제가 처음에 BFS로 할때는 시간초과가 났는데, 백트랙킹을 쓰니까 시간초과가 안 나더라구요....최단거리를 구할 때 백트랙킹이 더 좋은가요???

djm03178 5년 전 0

BFS로 시간 초과가 났다면 BFS를 잘못 짜신 겁니다. 제가 코드를 잘못 봤는데, 이건 O(N^2*M^2)이 아니라 지수복잡도네요. 아래와 같은 케이스만 넣어도 아주 아주 오랜 시간이 걸립니다.

그리고 최단 거리는 무조건 BFS입니다. 다음 글을 읽어보세요. https://www.acmicpc.net/board/...

그리고 질문을 올릴 때 위에 읽으라고 나오는 공지사항도 꼭 읽어보시기 바랍니다.

20 20
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000

kjho1037 5년 전 0

답변 감사합니다.

아래는 같은 방식으로 BFS로 실행한 것인데..

아무리 생각해도 BFS로 짠 것이 시간초과가 날 리가 없는데 계속납니다.

주변에 딱히 물어볼 사람도 없고해서ㅜ,ㅠ하루종일 고민해도 위에 코드는 통과하는데 아래 코드는 시간초과나는 이유를 모르겠습니다ㅜ,ㅠ

#include <stdio.h>
#include <string.h>

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

int M, N, MIN, Q_Front, Q_Back, Lenth;
int MAP[1111][1111];
int VISIT[1111][1111];
point Q[1000 * 1000];
int D[1000 * 1000];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,-1,1 };


void BFS(int arr[1111][1111])
{
	while (Q_Front != Q_Back)
	{
		int xx = Q[++Q_Front].x;
		int yy = Q[Q_Front].y;
		VISIT[yy][xx] = 1;

		for (int i = 0; i < 4; i++)
		{
			int xxx = xx + dx[i];
			int yyy = yy + dy[i];

			if (xxx == N && yyy == M)
			{
				if (D[Q_Back] + 1 < MIN)
					MIN = D[Q_Back] + 1;
				return;
			}
			else if (arr[yyy][xxx] == 0 && VISIT[yyy][xxx] == 0)
			{
				D[++Q_Back] = D[Q_Front] + 1;
				Q[Q_Back].y = yyy;
				Q[Q_Back].x = xxx;
				if (D[Q_Back] > MIN)
					return;
			}
		}
	}
}

int main()
{
	scanf("%d %d", &M, &N);
	memset(MAP, 1, sizeof(MAP));

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

	MIN = 99999999;
	Q_Front = -1;
	Q_Back = -1;
	Q[++Q_Back].x = 1;
	Q[Q_Back].y = 1;

	BFS(MAP);

	for (int i = 1; i <= M; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (MAP[i][j] == 0 || (i == 1 && j == 1))
				continue;

			if ((MAP[i + 1][j] == 1 || i + 1 > M) && 
				(MAP[i][j + 1] == 1 || j + 1 > N) && 
				(MAP[i - 1][j] == 1 || i - 1 < 1) && 
				(MAP[i][j - 1] == 1 || j - 1 < 1))//0으로 바꾸었는데, 사방에 1이면 노 필요~
				continue;

			memset(VISIT, 0, sizeof(VISIT));
			memset(Q, 0, sizeof(Q));
			memset(D, 0, sizeof(D));
			Q_Front = -1;
			Q_Back = -1;
			Q[++Q_Back].x = 1;
			Q[Q_Back].y = 1;

			MAP[i][j] = 0;
			BFS(MAP);
			MAP[i][j] = 1;
		}
	}

	if (MIN == 99999999)
	{
		printf("-1\n");
		return;
	}
	printf("%d\n", MIN + 1);

	return 0;
}

djm03178 5년 전 1

BFS는 큐에 넣을 때 방문했다는 표시를 해야 됩니다. 큐에서 뺀 다음에 하면 늦습니다. 여러 방향에서 어떤 칸으로 동시에 옮겨가려고 하면 무슨 일이 발생할까요?

위에 드린 케이스만 넣어봐도 큐의 크기를 한참 넘어가버리게 됩니다.

kjho1037 5년 전 0

답변 감사합니다!!!!

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

문제

문제

출처

ICPC

런타임오류..진짜 못 찾겠어요ㅜ,ㅠ

kjho1037 5년 전 0

djm03178 5년 전 1

kjho1037 5년 전 0

djm03178 5년 전 1

kjho1037 5년 전 0

djm03178 5년 전 0

kjho1037 5년 전 0

djm03178 5년 전 1

kjho1037 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말