글 읽기 - 메모리초과

tdj03063 3년 전 0

queue에 값이 너무 많이 들어가서 메모리 초과가 나는 것 같은데 어떻게 해결해야 할까요...

#include <cstring> // memset
#include <string> //string
#include <iostream> 
#include <queue>
#include <vector>

using namespace std;

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define MAX 100

int c, r;
string arr[MAX];
bool visit[MAX][MAX] = { false, };
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int bfs() {
	priority_queue<pair<int, pair<int, int > >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > q;
	q.push(make_pair(0, make_pair(0, 0)));
	visit[0][0] = true;

	while (!q.empty()) {
		int y = q.top().second.first;
		int x = q.top().second.second;
		int cnt = q.top().first;
		q.pop();

		if (y == c - 1 && x == r - 1) return cnt;

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny >= c || nx >= r || ny < 0 || nx < 0)	continue;

			if (!visit[ny][nx] && arr[ny][nx] == '1') 
				q.push(make_pair(cnt + 1, make_pair(ny, nx)));

			if (!visit[ny][nx] && arr[ny][nx] == '0') {
				q.push(make_pair(cnt, make_pair(ny, nx)));
				visit[ny][nx] = true;
			}
		}
	}
}

int main() {
	fastio;

	cin >> r >> c;
	for (int i = 0; i < c; i++) cin >> arr[i];

	cout << bfs();
}

wogus23 3년 전 0

000

010

이러한 데이터가 있을 때 (1,1)->(1,2)->(2,2)->(3,2)->(3,3) 경로 벽 :1

(1,1)->(1,2)->(2,2)->(2,3)->(3,3) 경로 벽 :0

위의 두 경로 중 작은 값을 출력한다는 보장이 있나요?

그리고

011

111

110

이러한 데이터가 있으면1만 있는 곳에서 cycle이 발생해서 메모리 초과가 발생하지 않나요?

(저도 잘 몰라서 질문하는 거에용)

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

문제

문제

출처

ICPC

메모리초과

tdj03063 3년 전 0

wogus23 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말