글 읽기 - [C++] 메모리 초과 계산 질문입니다.

kyr9389 2년 전 0

해당 문제를 다익스트라를 구현해서 풀어보려고 했는데, 메모리 초과를 받았습니다.

제 생각으로는 제한된 메모리 이상을 사용한것 같지는 않은데, 어느 부분에서 메모리가 많이 사용되었는지 모르겠어서 질문 드립니다.

아래는 제가 예상한 최대 메모리입니다.

---

int 변수 2개를 멤버로 가진 node 구조체 : (4*2) 8바이트 * 최대 간선(300,000) = 2,400,000 바이트
int arr[20001] = 4*20001 = 80,004 바이트
vector 컨테이너 (노드) 8바이트 * 20001 = 160,008 바이트
우선순위큐 컨테이너 (노드) 8바이트 * 20001 = 160,008 바이트

= 2.67mb

---

문제의 조건인 256mb에 못 미치는것 같은데, 어느 부분을 잘못 생각한건지 도움 주시면 감사하겠습니다.

아래에 메모리 초과가 발생했던 코드를 첨부합니다.

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

// 탐색에 필요한 노드 구조체 생성
struct node {
	int _end;
	int _cost = 999999999;
};

// 오름차순으로 정렬된 우선순위 큐를 위한 비교 함수
struct cmp {
	bool operator()(node a, node b) {
		return a._cost < b._cost;
	}
};

int arr[20001] = {0}; // 시작점으로부터 거리를 저장할 배열
vector<node> v[20001]; // 연결된 간선을 저장할 벡터
priority_queue<node, vector<node>, cmp> q; // 탐색을 진행할 오름차순 우선순위 큐

// 시작점 __start 로 부터 탐색 시작
void findPath(int __start) {
    // 시작점에서 연결된 배열들을 우선순위 큐에 추가
	for(auto i : v[__start]) {
		q.push(i);
	}
	
    // 전체 탐색
	while(!q.empty()) {
		int _end = q.top()._end;
		int _cost = q.top()._cost;
		q.pop();
		
        // 이전에 탐색한 정점이지만 더 짧은 경로로 도착했거나, 처음 탐색하는 경우 거리를 저장
		if(arr[_end] > _cost || (arr[_end] == 0 && _end != __start))
			arr[_end] = _cost;
		
        // 가장 가까운 정점이 처음 방문하거나 더 짧은 경로일경우, 큐에 추가
		for(auto i : v[_end]) {
			if(i._cost < arr[i._end] || (arr[i._end] == 0 && i._end != __start)) {
				node tmp;
				tmp._end = i._end;
				tmp._cost = _cost + i._cost; // 시작점에서부터의 거리 누적
				q.push(tmp);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int V, E, K, a, b, c;
	cin >> V >> E >> K;
	
	arr[K] = 0;
	for(int i = 0; i<E; i++) {
		cin >> a >> b >> c;
		
		node tmp;
		tmp._end = b;
		tmp._cost = c;
		v[a].push_back(tmp);
	}
	
	findPath(K);
	
	for(int i = 1; i<=V; i++) {
        // 탐색되지 않은 정점의 경우 끊어진것으로 판단, INF 출력
		if(arr[i] == 0 && i != K) cout << "INF" << '\n';
		else cout << arr[i] << '\n';
	}
}

djs100201 2년 전 1

다익스트라 부분에서 틀렸습니다.

kyr9389 2년 전 0

@djs100201 답변 감사합니다. 다익스트라를 살짝 수정해서 문제는 맞췄습니다.

그런데 메모리를 산출하는건 저렇게 하는게 맞는걸까요?

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

문제

문제

출처

ICPC

[C++] 메모리 초과 계산 질문입니다.

kyr9389 2년 전 0

djs100201 2년 전 1

kyr9389 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말