글 읽기 - 2178 미로탐색 12%에서 틀렸습니다 가 뜹니다

cheonilchu 5년 전 0

아까 잘못 올려서 다시 질문 드립니다!!

예제에 주어진 TC는 만족하지만 틀렸다고 나와서 질문 드립니다!

감사합니다.

#include <stdio.h>
#include <stdlib.h>

int map[101][101] = { 0 }, x[101] = { 0 }, y[101] = { 0 };
int front = 0, rear = 0;
int N, M;
int count[1000000] = { 0 };
int _x, _y;

int enqueue(int _a, int _b, int _c)
{
	x[rear] = _a;
	y[rear] = _b;
	count[rear] = _c;
	rear++;
}

int dequeue()
{
	front++;
}

int BFS(int _x, int _y)
{
	enqueue(_x, _y, 1);
	map[0][0] = 0;
	while (front < rear)
	{
		if (x[front] == M - 1 && y[front] == N - 1)
		{
			break;
		}
		map[y[front]][x[front]] = 0;
		if (map[y[front] + 1][x[front]] == 1 && y[front] < N - 1)
		{
			enqueue(x[front], y[front] + 1, count[front] + 1);
		}
		if (map[y[front]][x[front] + 1] == 1 && x[front] < M - 1)
		{
			enqueue(x[front] + 1, y[front], count[front] + 1);
		}
		if (map[y[front] - 1][x[front]] == 1 && y[front] > 0)
		{
			enqueue(x[front], y[front] - 1, count[front] + 1);
		}
		if (map[y[front]][x[front] - 1] == 1 && x[front] > 0)
		{
			enqueue(x[front] - 1, y[front], count[front] + 1);
		}
		dequeue();
	}
	if (front < rear)
	{
		printf("%d\n", count[front]);
	}
}

int main()
{

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

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

	BFS(0, 0);
	return 0;
}

djm03178 5년 전 0

제가 아까 답변드린 건 프로그램을 실행해보지 않고 드린 말씀이었습니다. 68번째 줄이 잘못됐다는 것이 명백하기 때문입니다. 이대로 두면 절대 예제가 잘 돌아갈 리가 없습니다. 예제에 없는 공백을 임의로 넣지 말고 테스트해보세요.

cheonilchu 5년 전 0

말씀하신 부분을

scanf("%1d", &map[i][j]); 로 한자리 숫자만 입력 받도록 했는데도 틀렸다고 나옵니다...

제가 제대로 이해한것이 맞는지 모르겠습니다 ㅠㅠ

djm03178 5년 전 0

일단 y[front]나 x[front]가 0보다 큰지를 체크하기 전에 먼저 배열의 해당 원소에 접근해버리면 안 됩니다. 이것만으로도 문제는 발생할 수 있습니다.

그리고 함수의 리턴형을 int로 설정했다면 뭔가 값을 반환을 해주는 것이 맞습니다. 이 경우에는 아무것도 리턴할 필요가 없으니 처음부터 void로 선언해주는 것이 맞습니다.

그리고 이 코드는 BFS를 수행할 때 중복 방문이 발생할 수 있습니다. 이미 방문한 곳은 다시 방문하지 않게 처리를 해줘야 합니다.

https://www.acmicpc.net/board/... 를 읽어보세요.

cheonilchu 5년 전 0

방금 해결 했습니다!!

정말 감사합니다!!!!!!

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

문제

문제

출처

ICPC

2178 미로탐색 12%에서 틀렸습니다 가 뜹니다

cheonilchu 5년 전 0

djm03178 5년 전 0

cheonilchu 5년 전 0

djm03178 5년 전 0

cheonilchu 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말