글 읽기 - BFS로 구현하였고 다 잘한거 같은데 왜 시간초과가 뜰까요??

whoareyou 4년 전 0

visited도 큐에 넣을때 하였고 일부러 배열크기도 하나씩 늘려서 잡았는데 왜 시간 초과가 뜰까요??도대체 뭐가 문제일까요...

#include<stdio.h>
#include<stdlib.h>
int N, M;
int maze[101][101];
int visited[101][101] = { 0, };
int queuex[10001];
int queuey[10001];
int distance[101][101] = { 0 };
int front = 0, rear = 0;
int bfs(int y, int x);//N이 세로 M이 가로;
int dequeuey();
int dequeuex();
void enqueue(int y, int x);
int isEmpty();
int main(void) {
	int i, j,depth=0;
	char arr[101];
	scanf("%d %d%*c", &N, &M);
	for (i = 0; i < N; i++)
	{
		gets(arr);
		for (j = 0; j < M; j++)
			maze[i][j] = arr[j]-'0';
	}
	int y = 0, x = 0;
	distance[y][x] = 1;
	while(1)
	{
		visited[y][x] = 1;
		if (y == N - 1 && x == M - 1) {
			break;
		}
		if (y + 1 < N)
			if (visited[y + 1][x] == 0 && maze[y + 1][x] == 1)
			{
				distance[y + 1][x] = distance[y][x] + 1;
				enqueue(y + 1, x);
			}
		if (x + 1 < M)
			if (visited[y][x + 1] == 0 && maze[y][x + 1] == 1)
			{
				distance[y][x + 1] = distance[y][x] + 1;
				enqueue(y, x + 1);
			}
		if (y - 1 >= 0)
			if (maze[y - 1][x] == 1 && visited[y - 1][x] == 0)
			{
				distance[y - 1][x] = distance[y][x] + 1;
				enqueue(y - 1, x);
			}
		if (x - 1 >= 0)
			if (maze[y][x - 1] == 1 && visited[y][x - 1] == 0)
			{
				distance[y][x - 1] = distance[y][x] + 1;
				enqueue(y, x - 1);
			}
		x = dequeuex();
		if (x != -1)
			y = dequeuey();
		else
			break;
	}
	printf("%d\n",distance[N-1][M-1]);
}
void enqueue(int y, int x)
{
	maze[y][x] = 0;
	rear = ++rear % 10001;
	queuey[rear] = y;
	queuex[rear] = x;
}
int dequeuex()
{
	int tmp;
	if (isEmpty())
		return -1;
	front = front++ % 10001;
	return queuex[front];
}
int dequeuey()
{
	return queuey[front];
}
int isEmpty()
{
	return front == rear;
}

djm03178 4년 전 1

큐에 넣을 때 방문 체크를 해야 한다는 말은 visited[y][x] = 1; 이 문장이 큐에 넣을 때 큐에 넣는 좌표에 대해 수행되어야 한다는 뜻입니다.

whoareyou 4년 전 0

답변 너무 감사드립니다.앗!!죄송합니다. 제가 소스 코드를 잘못 붙여넣었습니다. 이렇게 enqueue안에서 visited[y][x]=1하였는데도 시간초과가 뜨는데 어디서 문제인걸까요??

#include<stdio.h>
#include<stdlib.h>
int N, M;
int maze[101][101];
int visited[101][101] = { 0, };
int queuex[10001];
int queuey[10001];
int distance[101][101] = { 0 };
int front = 0, rear = 0;
int bfs(int y, int x);//N이 세로 M이 가로;
int dequeuey();
int dequeuex();
void enqueue(int y, int x);
int isEmpty();
int main(void) {
	int i, j,depth=0;
	char arr[101];
	scanf("%d %d%*c", &N, &M);
	for (i = 0; i < N; i++)
	{
		gets(arr);
		for (j = 0; j < M; j++)
			maze[i][j] = arr[j]-'0';
	}
	int y = 0, x = 0;
	distance[y][x] = 1;
	while(1)
	{
		if (y == N - 1 && x == M - 1) {
			break;
		}
		if (y + 1 < N)
			if (visited[y + 1][x] == 0 && maze[y + 1][x] == 1)
			{
				distance[y + 1][x] = distance[y][x] + 1;
				enqueue(y + 1, x);
			}
		if (x + 1 < M)
			if (visited[y][x + 1] == 0 && maze[y][x + 1] == 1)
			{
				distance[y][x + 1] = distance[y][x] + 1;
				enqueue(y, x + 1);
			}
		if (y - 1 >= 0)
			if (maze[y - 1][x] == 1 && visited[y - 1][x] == 0)
			{
				distance[y - 1][x] = distance[y][x] + 1;
				enqueue(y - 1, x);
			}
		if (x - 1 >= 0)
			if (maze[y][x - 1] == 1 && visited[y][x - 1] == 0)
			{
				distance[y][x - 1] = distance[y][x] + 1;
				enqueue(y, x - 1);
			}
		x = dequeuex();
		if (x != -1)
			y = dequeuey();
		else
			break;
	}
	printf("%d\n",distance[N-1][M-1]);
}
void enqueue(int y, int x)
{
	visited[y][x] = 1;
	maze[y][x] = 0;
	rear = ++rear % 10001;
	queuey[rear] = y;
	queuex[rear] = x;
}
int dequeuex()
{
	int tmp;
	if (isEmpty())
		return -1;
	front = front++ % 10001;
	return queuex[front];
}
int dequeuey()
{
	return queuey[front];
}
int isEmpty()
{
	return front == rear;
}

djm03178 4년 전 1

68, 77번째 줄과 같은 문장은 실제로 rear, front가 언제 증가될지 보장해주지 않습니다. ++ 대신 + 1로 바꾸어주면 맞습니다.

whoareyou 4년 전 0

너무 감사합니다!! 원형 큐에대한 이해가 아직 부족한것 같습니다. 답변 감사드립니다.

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

문제

문제

출처

ICPC

BFS로 구현하였고 다 잘한거 같은데 왜 시간초과가 뜰까요??

whoareyou 4년 전 0

djm03178 4년 전 1

whoareyou 4년 전 0

djm03178 4년 전 1

whoareyou 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말