글 읽기 - 디익스트라 함수 반환값을 배열 주소로 했는데 계속 런타임 에러가 뜹니다

ttiger0114 3년 전 0

디익스트라 함수를 a,b의 최솟값을 반환하도록 하는 것이 아니라 a가 갈수 있는 모든 정점의 최소 거리를 가진 배열의 주소를 반환하도록 하였습니다.

이렇게 한 이유는 각 정점간의 거리를 반환할 경우 디익스트라 계산을 5번해야 하지만 정점이 갈수 있는 모든 경우를 반환할 경우 계산을 세번만 하면 되기 때

문에 최초에 이렇게 했으나 계속 런타임 오류가 걸려 그냥 함수 전체를 유지한 채로 반환값만 정점간의 거리를 반환하도록 하니 디익스트라 알고리즘의 횟수

가 증가했는데도 불구하고 런타임에러가 걸리지 않으며 정답처리가 되었습니다. 계산상의 오류가 마땅히 없는것 같은데 이러한 이유가 왜 일어나는지 궁금합

니다

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

using namespace std;

#define inf 987654321
vector<pair<int, int>> map[801];

int v, e, a, b;
int onetoa, onetob, atob, vtoa, vtob;

int* dijkstra(int a) {// 반환값을 a로 부터 모든 정점으로 가는 최소 거리 정보를 가진 배열주소로 했습니다
	int route[801];
	priority_queue<pair<int, int>> pq;

	for (int i = 1; i <= v; i++)
		route[i] = inf;
	route[a] = 0;
	pq.push(make_pair(0, a));

	while (!pq.empty()) {
		int cur = pq.top().second;
		int dis = -pq.top().first;
		pq.pop();
		for (int i = 0; i < map[cur].size(); i++) {
			int next = map[cur][i].second;
			int nextdis = dis + map[cur][i].first;

			if (nextdis < route[next]) {
				route[next] = nextdis;
				pq.push(make_pair(-nextdis, next));
			}
		}
	}
	return route;
    //input을 a,b로 받고 return route[b] 를 하여 a,b의 최소거리를 반환할 경우 정답이 됩니다
}

int main() {
	int ret;
	int* temp;
	cin >> v >> e;
	for (int i = 0; i < e; i++) {
		int st, des, w;
		scanf("%d %d %d",&st,&des,&w);
		map[st].push_back(make_pair(w, des));
		map[des].push_back(make_pair(w, st));
	}
	cin >> a >> b;
	temp = dijkstra(1);
	onetoa = temp[a], onetob = temp[b];
	if (onetoa == inf && onetob == inf) {
		cout << -1; 
		return 0 ;
	}

	temp = dijkstra(a);
	atob = temp[b];
	if (atob == inf) {
		cout << -1;
		return 0;
	}


	temp = dijkstra(v);
	vtoa = temp[a], vtob = temp[b];
	
	ret = min(onetoa + atob + vtob, onetob + atob + vtoa);

	if (ret >= inf)
		ret = -1;
	cout << ret;
	return 0;

}

djm03178 3년 전 1

route는 지역으로 선언된 배열이므로 dijkstra 함수가 종료되는 순간 함께 소멸되는 배열입니다. 따라서 이 주소에 이후에 접근하려고 하면 안 됩니다.

ttiger0114 3년 전 0

몇몇 예제에서 잘 돌아가서 제가 잠시 함수가 끝나도 주소 내용물이 남는다고 착각하고 있었네요.. 그러면 함수가 끝나는 순간 그 안의 정보는 전부 사라지는 건가요? 아니면 그 정보는 계속 해당 주소에 남겨져 있다가 나중에 덮어씌워져서 오류가 나는건가요?

ttiger0114 3년 전 0

배열 주소를 반환하는 함수의 경우 끝나고 해당 주소안의 정보가 덮어씌워질 우려가 있기 때문에 함수의 결과로 배열을 얻고 싶어서 주소를 반환하는 함수가 위험한 문법이라면 그것과 다르게 배열을 반환하는 방법이 있을까요??

djm03178 3년 전 0

원칙적으로 쓰면 안 되는 방식이기 때문에 컴퓨터가 실제로 그 주소에 어떤 처리를 해놓았을지는 아예 모른다고 하는 편이 좋습니다. 현실적으로 보자면 그 주소에 해당하는 페이지 자체가 운영체제에 의해 회수되었을 수도 있고, 다른 정보가 덮어씌워졌을 수도 있습니다.

이런 경우 보통 사용하는 방법이 동적 할당이고, 그 역할을 간편하게 해내도록 설계된 것이 바로 vector입니다.

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

문제

문제

출처

ICPC

디익스트라 함수 반환값을 배열 주소로 했는데 계속 런타임 에러가 뜹니다

ttiger0114 3년 전 0

djm03178 3년 전 1

ttiger0114 3년 전 0

ttiger0114 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말