글 읽기 - 다익스트라 문제 15%에서 메모리초과가 납니다

yoohoo030 1년 전 0

질문게시판 보면서 최대한 수정했는데 계속해서 메모리초과가 나네요ㅠㅠ

몇시간째 수정해도 답이 안나와서 질문 올립니다. 도와주세요 고수님들😭

#include <iostream>
#include <queue>
#define INF 1e9
using namespace std;
vector<vector<pair<long long, int>>> node; // 노드 간의 관계를 담은 벡터
long long c[1001]; // 비용 배열
int path[1001]; // 이전에 거쳐온 도시 번호를 저장하는 배열

void dijkstra(int cost, int city, int dest) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ cost, city });
	c[city] = 0;
	path[city] = 0;
	while (!pq.empty()) {
		long long cost = pq.top().first;
		int city = pq.top().second;
		pq.pop();
		if (city == dest) {
			cout << c[city] << '\n';
			return;
		}
		if (cost > c[city]) continue;
		for (int i = 0; i < node[city].size(); i++) {
			long long n_cost = node[city][i].first;
			int n_city = node[city][i].second;
			if (c[n_city] > cost + n_cost) {
				pq.push({ cost + n_cost, n_city });
				c[n_city] = cost + n_cost;
				path[n_city] = city;
			}
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int n, m, start, dest;
	vector<int> p;
	cin >> n >> m;
	node.assign(n + 1, vector<pair<long long, int>>()); // 메모리초과 방지 (벡터 동적할당)
	for (int i = 0; i < m; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		node[from].push_back({ cost, to });
	}
	for (int i = 1; i <= n; i++)
		c[i] = INF;
	cin >> start >> dest;
	dijkstra(0, start, dest);
	// 경로 구하기
	p.push_back(dest);
	for (int i = dest; i != 1; i = path[i]) // path[도시] = 이전 도시 / 경로를 p 벡터에 넣음
		p.push_back(path[i]);
	cout << p.size() << '\n';
	for (int i = p.size() - 1; i >= 0; i--) // 거꾸로 출력
		cout << p[i] << ' ';
}

wizardrabbit 1년 전 1

안녕하세요? 디버깅 결과, for문의 종료조건이 잘못되어 경로를 역추적하는 과정에서 무한루프가 돌 수 있음을 확인했습니다.

for (int i = dest; i != 1; i = path[i])

경로를 역추적하는 for문인 52번째 줄의 종료 조건은 i 값이 1인 경우인데, 이 경우 시작하는 정점의 번호가 1이 아닌 경우 탐색 경로에 1번 정점이 들어가지 않는 케이스가 생길 수 있는데, 이 경우 1번 정점을 찾지 못 해 for문이 종료되지 못하고 무한 루프를 돌 수 있습니다.

우리가 원하는 것은 경로의 시작인 시작 정점을 만났을 때 경로 탐색을 멈추고 종료하는 것이니, 종료 조건을 시작 정점을 만났을 때로 변경해 주시면 문제를 맞추실 수 있습니다.

궁금증이 해결되셨기를 바랍니다!

yoohoo030 1년 전 1

헉 제가 왜 시작 지점이 1이라고 착각했을까요..!! ㅠㅠ 시간초과도 아니고 메모리초과길래 제가 코드를 잘못 써서 무한루프가 도는 거라고는 생각을 못했습니다. 말씀하신 부분 수정하니까 바로 정답처리 되네요!! 정말 너무너무 감사합니다!!!

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

문제

문제

출처

ICPC

다익스트라 문제 15%에서 메모리초과가 납니다

yoohoo030 1년 전 0

wizardrabbit 1년 전 1

yoohoo030 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말