백준 1753번 최단경로 C++

이 문제를 20001 x 20001 크기의 이차원 배열을 선언해서 풀었더니 메모리 초과가 났다.

이 코드를 돌리려면 1.6기가바이트가 필요하다고 한다. → 20001 x 20001 x 4(byte) = 1.6GB

이 문제의 메모리 제한은 256MB 이다.

 

메모리 초과 코드

#include <iostream>
using namespace std;

int minW[20001][20001]{};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int v, e, k;
	cin >> v >> e >> k;

	for (int i = 1; i <= v; ++i)
		for (int j = 1; j <= v; ++j)
			minW[i][j] = 11;

	for (int i = 0; i < e; ++i) {
		int u, v, w;
		cin >> u >> v >> w;

		minW[u][v] = w;
		minW[k][v] = min(minW[k][v], minW[k][u] + w);
	}

	for (int i = 1; i <= v; ++i) {
		if (i == k)
			cout << "0" << "\n";
		else if (minW[k][i] == 11)
			cout << "INF" << "\n";
		else
			cout << minW[k][i] << "\n";
	}

	return 0;
}

 

 

다익스트라 - 우선순위 큐 + DP 

다익스트라를 활용한 정답 코드

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

#define INF 1e9
#define MAX_VERTEX 20001

vector<pair<int, int>> edge[MAX_VERTEX];
int d[MAX_VERTEX]{};

void Dijkstra(int start) {
	d[start] = 0;

	// 가중치가 작은 값을 먼저 꺼내야 while이 더 적게 돌기 때문에 
	// 비용이 적은 것이 top으로 가도록 우선순위 큐 선언 
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	
	// 가장 먼저, 시작하는 정점을 큐에 넣어
    // 시작 정점에서 출발하는 간선, 도착 정점을 큐에 들어갈 수 있도록 한다.
	pq.push({ 0, start });

	while (!pq.empty()) {
		int cur = pq.top().second; // 지금 정점
        
        // 그 전에 while문을 돌았다면, 그때의 정점을 거친 지금 정점까지의 거리
        // 최소 비용일 수도, 아닐 수도 있음
		int distance = pq.top().first; 

		pq.pop(); // 정보 저장 후 pop

		if (d[cur] < distance) // distance가 저장된 비용보다 크다면 continue;
			continue;

		// 지금 정점에서 출발하는 모든 간선들 체크
		for (int i = 0; i < edge[cur].size(); ++i) {
			int next = edge[cur][i].first;
			int nextDistance = distance + edge[cur][i].second;
			
			// 만약 nextDistance가 최소 비용이라면 d 업데이트, 업데이트된 비용과 다음 정점을 큐에 저장
			if (d[next] > nextDistance) {
				d[next] = nextDistance;

				pq.push({ nextDistance, next });
			}
		}
	}
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int v, e, k;
	cin >> v >> e >> k;

	for (int i = 1; i < v + 1; ++i)
		d[i] = INF;

	for (int i = 0; i < e; ++i) {
		int u, v, w;
		cin >> u >> v >> w;

		edge[u].push_back(make_pair( v, w ));
	}

	Dijkstra(k);

	for (int i = 1; i <= v; ++i) {
		if (d[i] == INF)
			cout << "INF" << "\n";
		else
			cout << d[i] << "\n";
	}

	return 0;
}

 

우선순위 큐 안에는 거리(w)가 first에 있어야 함에 주의

second에 넣었다가 시간 초과 떴다.

 

https://www.acmicpc.net/problem/1753