글 읽기 - [C++] 왜 메모리 초과가 나는지 잘 모르겠습니다 ㅜㅜ

37sadan_tongsinbyung 3년 전 0

첨부된 소스코드와 같이 작성하였는데 192MB를 쓸것 같지는 않은데 메모리초과가 나와서 슬픕니다 ㅜㅜ

#include <stdio.h>
#include <queue>
using namespace std;
int main() {
	int n, m, arr[101][101] = { 0, };
	bool visit[101][101] = { 0, };
	int _x[4] = { 0, 1, 0, -1 };
	int _y[4] = { -1, 0, 1, 0 };
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			scanf("%1d", &arr[i][j]);
	queue<pair<int, int>> q;
	pair<int, int> goal = make_pair(n, m);
	q.push(make_pair(1,1));
	while(!q.empty()) {
		pair<int,int> now = q.front();
		visit[now.first][now.second] = 1;
		int dist = arr[now.first][now.second];
		if(now == goal) {
			printf("%d\n", dist);
			return 0;
		}
		q.pop();
		for(int i = 0; i < 4; i++) {
			int x = now.first + _x[i];
			int y = now.second + _y[i];
			if(x > 0 && x <= n && y > 0 && y <= m) {
				if(arr[x][y] && !visit[x][y]) {
					q.push(make_pair(x, y));
					arr[x][y] = dist+1;
				}
			}
		}
	}
	return 0;
}

ghkdiwl 3년 전 6

visit을 방문한다음에 찍어주게되면

아직 방문하지 않은 지점이 여러번 푸시될 수가 있어요

1 1

이렇게 있다치면

(1,2) (2,1) 지점에서 각각 (2,2)를 큐에 두번 push하게 돼요

그래서 큐에 집어넣으면서 visit을 찍어줘야 (2,2)에 중복 방문하지 않아서 메모리 초과가 안나요

좀 지난글이지만 저도 같은 실수 해가지고 적어봅니다.

#include <stdio.h>
#include <queue>
using namespace std;
int main() {
	int n, m, arr[101][101] = { 0, };
	bool visit[101][101] = { 0, };
	int _x[4] = { 0, 1, 0, -1 };
	int _y[4] = { -1, 0, 1, 0 };
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%1d", &arr[i][j]);
	queue<pair<int, int>> q;
	pair<int, int> goal = make_pair(n, m);
	q.push(make_pair(1, 1));
	while (!q.empty()) {
		pair<int, int> now = q.front();
		int dist = arr[now.first][now.second];
		if (now == goal) {
			printf("%d\n", dist);
			return 0;
		}
		q.pop();
		for (int i = 0; i < 4; i++) {
			int x = now.first + _x[i];
			int y = now.second + _y[i];
			if (x > 0 && x <= n && y > 0 && y <= m) {
				if (arr[x][y] && !visit[x][y]) {
					q.push(make_pair(x, y));
					visit[x][y] = 1;
					arr[x][y] = dist + 1;
				}
			}
		}
	}
	return 0;
}

37sadan_tongsinbyung 3년 전 0

감사합니다 ㅜㅜ 그부분 생각 못하고 있었네요...

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

문제

문제

출처

ICPC

[C++] 왜 메모리 초과가 나는지 잘 모르겠습니다 ㅜㅜ

37sadan_tongsinbyung 3년 전 0

ghkdiwl 3년 전 6

37sadan_tongsinbyung 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말