글 읽기 - 2178번 미로탐색 어디가 문제일까요?

gkfkagkfka12 6년 전 0

댓글보고 질문검색 다 찾아보고 실행해서 왔습니다.

반례는 없는 것 같은데 메모리초과가 발생하네요 ㅠㅠ 메모리 초과가 중복 방문 때문에 발생한다고 하던데

저는 visited 배열로 한 번 방문한 곳은 방문하지 않게 짰는데 왜이럴까요?

#include <cstdio>
#include <queue>
#include <algorithm>

int maze[101][101];
bool visited[101][101];
char s[101];

struct Pos {
	int x;
	int y;
	int length;
};

int main(void)
{
	int n, m; scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%s", s);
		for (int j = 0; j < m; j++) {
			maze[i][j+1] = s[j] - '0';
			visited[i][j+1] = false;
		}
	}

	// 시작지점 초기화해서 큐에 넣기
	Pos begin = { 1,1,1 };
	std::queue<Pos> path;
	path.push(begin);

	int x = 0, y = 0;
	int len = 1;
	int ans = 0;

	while (!path.empty()) {
		x = path.front().x; y = path.front().y;
		printf("maze[%d][%d] 방문\n", x, y);
		len = path.front().length;
		if (x == n && y == m) {
			ans = len;
			break;
		}
		path.pop();
		visited[x][y] = true;

		// 위쪽
		if (x - 1 >= 1 && maze[x-1][y]==1 && visited[x - 1][y] == false) {
			Pos up = { x - 1,y,len+1 };
			path.push(up);
		}
		// 아래쪽
		if (x + 1 <= n && maze[x+1][y] == 1 && visited[x + 1][y] == false) {
			Pos down = { x + 1,y,len + 1 };
			path.push(down);
		}
		// 왼쪽
		if (y-1>=1 && maze[x][y-1] == 1 && visited[x][y - 1] == false) {
			Pos left = { x,y - 1,len + 1 };
			path.push(left);
		}
		if (y + 1 <=m && maze[x][y+1] == 1 && visited[x][y + 1] == false) {
			Pos right = { x,y+1,len + 1 };
			path.push(right);
		}
	}

	printf("%d", ans);



	return 0;
}

jh05013 6년 전 1

https://www.acmicpc.net/board/...
"질문 검색을 먼저 해서 자신에게 필요한 답변이나 반례가 없는지 확인하고 질문을 남겨주세요."

gkfkagkfka12 6년 전 0

충고 감사합니다. 수정했습니다. 다시한번 봐주실수있나요?

jh05013 6년 전 1

여전히 게시판에 답변이 있습니다.

gkfkagkfka12 6년 전 0

한 지점을 방문할 때마다 방문했다고 표시했는데 상/하/좌/우를 큐에 넣을 때 방문했다고 표시해서 맞았습니다.

그런데 혹시 제 이해가 맞는건가요?

한 지점마다 방문했다고 표시하면 상/하/좌/우를 큐에 넣을 때마다 아직 방문이 안되었다고 표시된 부분이 있기 때문에 중복해서 방문하게 된다는 걸로 이해했습니다.

맞나요??

jh05013 6년 전 1

네, BFS 방문 표시는 큐에서 뺄 때가 아닌 넣을 때 해야 중복 방문이 일어나지 않습니다. BFS에서 많은 사람들이 하는 실수입니다. BFS 문제에서 메모리 초과가 나면 대부분은 이것 때문이라고 볼 수 있습니다.

gkfkagkfka12 6년 전 0

정말 감사합니다! 제가 대학교 3학년으로 BFS와 DFS, 위상정렬 연습을 하려고 하는데 그냥 단계별로 풀면 되려나요?

혹시 추천해주실 문제 있으신가요? 죄송합니다 ㅠ

jh05013 6년 전 1

개인적으로 단계별로 풀어보기에는 이상한 문제가 좀 끼여 있다고 생각합니다. 이런 거라든지...

그래서 제가 이것과 비슷한 취지의 문제집을 만든 적이 있습니다.

https://www.acmicpc.net/workbo...

"DFS와 BFS"부터 "벽 부수고 이동하기"까지가 BFS/DFS이고, "줄 세우기"부터 "음악프로그램"까지가 위상정렬입니다.

gkfkagkfka12 6년 전 1

우와 정말 감사드립니다! k번째 숫자는 너무 어려운 문제였습니다..ㅠㅠ

친절한 답변 감사합니다. 좋은하루되세여~

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