[C++] 최소비용 구하기2

백준 11779번

 

다익스트라로 풀어본 최소비용 구하기 문제

가장 기본적인 다익스트라는 거리(비용)만 구하는데 경로까지 구해야 하는 문제였다

경로를 우선순위큐에 vector로 다 넣어주었는데 간단하게 풀고싶어서 그렇게 풀긴 했지만 좋은 풀이는 아닌 것 같다

 

메모리를 줄이기 위해 다른 풀이가 있는지 찾아보았더니 특정점 a를 가기 위한 최적 경로가 b를 통해서라면 route[a] = b와 같이 저장해서 쓰는 방법이 있었다

이렇게하면 모든 경로를 벡터로 갖지 않아도 역추적이 가능하다

 

#include <stdio.h>
#include <queue>
#include <vector>
 
using namespace std;
 
vector<pair<int,int> > graph[1005]; // [from] to, cost
int visit[1005];
priority_queue<pair<pair<int,int>,vector<int> > > pq; // cost * -1, pos
 
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
 
    for(int i = 1 ; i <= m ; i++){
        int from,to,cost;
        scanf("%d %d %d",&from,&to,&cost);
        graph[from].push_back(make_pair(to,cost));
    }
 
    int start,end;
    scanf("%d %d",&start,&end);
    
    for(int i = 1 ; i <= n ; i++) visit[i] = -1;
    visit[start] = 0;
    vector<int> tmp;
    tmp.push_back(start);
    pq.push(make_pair(make_pair(0,start),tmp));
    while(!pq.empty()){
        int now = pq.top().first.second;
        int sum = pq.top().first.first * -1;
        vector<int> route = pq.top().second;
        pq.pop();
 
        if(now==end){
            printf("%d\n%d\n",sum,route.size());
            for(int i = 0 ; i < route.size() ; i++){
                printf("%d ",route[i]);
            }
            return 0;
        }
        for(int i = 0 ; i < graph[now].size() ; i++){
            int next = graph[now][i].first;
            int cost = graph[now][i].second;
            if(visit[next]==-1 || visit[next]>sum+cost){
                visit[next] = sum+cost;
                vector<int> tmp;
                for(int j = 0 ; j < route.size() ; j++){
                    tmp.push_back(route[j]);
                }
                tmp.push_back(next);
                pq.push(make_pair(make_pair((sum+cost)*-1,next),tmp));
            }
        }
    }
}

 

이건 처음 벡터로 모든 경로를 저장한 풀이

 

#include <stdio.h>
#include <queue>
#include <stack>
#include <vector>
 
using namespace std;
 
vector<pair<int,int> > graph[1005]; // [from] to, cost
int visit[1005];
priority_queue<pair<int,int> >  pq; // cost * -1, pos
int route[1005];
 
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
 
    for(int i = 1 ; i <= m ; i++){
        int from,to,cost;
        scanf("%d %d %d",&from,&to,&cost);
        graph[from].push_back(make_pair(to,cost));
    }
 
    int start,end;
    scanf("%d %d",&start,&end);
    
    for(int i = 1 ; i <= n ; i++) visit[i] = -1;
    visit[start] = 0;
    pq.push(make_pair(0,start));
    while(!pq.empty()){
        int now = pq.top().second;
        int sum = pq.top().first * -1;
        pq.pop();
 
        if(now==end){
            stack<int> route_ans;
            route_ans.push(end);
            while(now!=start){
                route_ans.push(route[now]);
                now = route[now];
            }
            printf("%d\n%d\n",sum,route_ans.size());
            while(!route_ans.empty()){
                printf("%d ",route_ans.top());
                route_ans.pop();
            }
            return 0;
        }
        for(int i = 0 ; i < graph[now].size() ; i++){
            int next = graph[now][i].first;
            int cost = graph[now][i].second;
            if(visit[next]==-1 || visit[next]>sum+cost){
                visit[next] = sum+cost;
                route[next] = now;
                pq.push(make_pair((sum+cost)*-1,next));
            }
        }
    }
}

 

이건 경로를 역추적한 풀이

 

 

메모리와 시간이 줄어든 것을 볼 수 있다