글 읽기 - 이게 왜 메모리초과일까요?..

jinhc0822 3년 전 0

예제입력의 첫번째, 세번째 테스트케이스는 답이 잘 나오는 반면 두번째 케이스에서 계속 답이 안 떠서 시간초과인가? 싶었는데 그냥 답안 제출을 해보니 메모리초과라고 뜨네요?.. 혹시 이게 왜 메모리 초과일까요? 그리고 원래 메모리 초과면 vs에서 실행 시에 시간초과 마냥 무한로딩인가요?

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int dy[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int dx[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
bool visit[300][300];

struct Pos{
	int y, x, c;
};

void bfs() {
	int l, y, x, targetY, targetX;
	queue<Pos> q;
	cin >> l >> y >> x >> targetY >> targetX;
	Pos cur = { y, x, 0 };
	q.push(cur);
	while (!q.empty()) {
		cur = q.front();
		visit[cur.y][cur.x] = true;
		q.pop();
		if (cur.y == targetY && cur.x == targetX) {
			cout << cur.c << '\n';
			break;
		}
		for (int i = 0; i < 8; i++) {
			int nextY = cur.y + dy[i];
			int nextX = cur.x + dx[i];
			if (nextY < 0 || nextY >= l || nextX < 0 || nextX >= l) continue;
			if (visit[nextY][nextX]) continue;
			q.push({ nextY, nextX, cur.c + 1 });
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
		memset(visit, false, sizeof(visit));
		bfs();
	}
}

jh0956 3년 전 1

bfs 탐색 진행간에

22줄처럼 방문확인 없이 방문처리를 해주시면

방문했던 곳을 재방문할테니 메모리초과가 발생할 수 밖에 없습니다.

https://www.acmicpc.net/source...

위 코드는 질문자님 코드를 수정한 것으로 방문처리를 확인한 후 제출하니 정답처리 되네요

jinhc0822 3년 전 0

nextX, nextY를 생성하기 전에 한 번 확인을 해야하는데 그걸 안 해서 메모리 초과가 일어났군요. 궁금증이 해결됐습니다. 질문한지 꽤 됐는데 답장해 주셔서 감사합니다!..

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

문제

문제

출처

ICPC

이게 왜 메모리초과일까요?..

jinhc0822 3년 전 0

jh0956 3년 전 1

jinhc0822 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말