글 읽기 - 메모리 초과의 이유

ldg1291 5년 전 0

일반적인 다익스트라로 풀었습니다만...

계속 메모리 초과가 납니다.

결국 큐에 너무 많이 쌓인다는것인데.. 여기서 메모리 활용을 더 줄일 방법이 있을까요??

도저히 모르겠어서 질문 드립니다

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int map[102][102];
int visited[102][102];
int N, M;
void bfs(int destx, int desty) {

	priority_queue < pair<int, pair<int, int>>> que;
	que.push(make_pair(0, make_pair(0, 0)));

	while (!que.empty()) {
		pair<int, int> nowPos = que.top().second;
		int dist = -1*que.top().first;

		que.pop();

		if (dist > visited[nowPos.first][nowPos.second]) {
			continue;
		}
		
		if (nowPos.first - 1 >= 0) {
			if (visited[nowPos.first - 1][nowPos.second] > dist + map[nowPos.first][nowPos.second]) {
				visited[nowPos.first - 1][nowPos.second] = dist + map[nowPos.first][nowPos.second];
				que.push({ -1 * visited[nowPos.first - 1][nowPos.second], {nowPos.first - 1, nowPos.second} });
			}
		}
		if (nowPos.second - 1 >= 0) {
			if (visited[nowPos.first][nowPos.second - 1] > dist + map[nowPos.first][nowPos.second]) {
				visited[nowPos.first][nowPos.second - 1] = dist + map[nowPos.first][nowPos.second];
				que.push({ -1 * visited[nowPos.first][nowPos.second - 1], {nowPos.first, nowPos.second - 1} });
			}
		}
		if (nowPos.first + 1 < M) {
			if (visited[nowPos.first + 1][nowPos.second] > dist + map[nowPos.first][nowPos.second]) {
				visited[nowPos.first + 1][nowPos.second] = dist + map[nowPos.first][nowPos.second];
				que.push({ -1 * visited[nowPos.first + 1][nowPos.second], {nowPos.first + 1, nowPos.second} });
			}
		}
		if (nowPos.second + 1 < N) {
			if (visited[nowPos.first][nowPos.second + 1] > dist + map[nowPos.first][nowPos.second]) {
				visited[nowPos.first][nowPos.second + 1] = dist + map[nowPos.first][nowPos.second];
				que.push({ -1 * visited[nowPos.first][nowPos.second + 1], {nowPos.first, nowPos.second + 1} });
			}
		}
	}
}

int main()
{
	scanf("%d %d", &N, &M);

	for (int i = 0; i < M; i++) {

		int tmp;
		scanf("%d", &tmp);

		for (int j = N-1; j >= 0; j--) {
			visited[i][j] = 0x7fffffff;
			map[i][j] = tmp % 10;
			tmp /= 10;
		}
	}

	visited[0][0] = 0;

	bfs(M - 1, N - 1);

	cout << visited[M - 1][N - 1]  << endl;
}

djm03178 5년 전 0

100자로 이루어진 정수는 %d로 받을 수 없습니다. int는 21억 정도 (2.1*10^9) 정도밖에 입력받지 못하는데, 입력되는 정수는 최대 약 10^99입니다.

정수 하나씩 떼어서 입력받는 법을 생각해보세요. 또는, 정수로 생각하지 말고 문자열로 생각해 보세요.

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

문제

문제

출처

ICPC

메모리 초과의 이유

ldg1291 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말