[Algorithm] Baekjoon 11779번 : 최소비용 구하기 2

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

11779번: 최소비용 구하기 2

struct Node
{
    int node;
    long long distance;
};
 
struct cmp
{
    bool operator() (const Node& a, const Node& b)
    {
        return a.distance > b.distance;
    }
};
 
long long dist[1001];
int v, e, a, b, c, start, dest;
vector<vector<Node>> graph(1001);
long long shortestDistance = 0;
int shortestParent[1001] = { 0 };
 
long long getShortestDistance()
{
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<Node, vector<Node>, cmp > pq;
    dist[start] = 0;
    pq.push({ start,0 });
 
    while (!pq.empty())
    {
        int curNode = pq.top().node;
        long long curDistance = pq.top().distance;
        pq.pop();
 
        if (dist[curNode] < curDistance) continue;
 
        for (int i = 0; i < graph[curNode].size(); ++i)
        {
            int nextNode = graph[curNode][i].node;
            long long nextDistance = graph[curNode][i].distance + curDistance;
 
            if (nextDistance < dist[nextNode])
            {
                shortestParent[nextNode] = curNode;
                dist[nextNode] = nextDistance;
                pq.push({ nextNode,nextDistance });
            }
        }
    }
 
    return dist[dest];
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> v >> e;
 
    for (int i = 0; i < e; ++i)
    {
        cin >> a >> b >> c;
        graph[a].push_back({ b,c });
    }
 
    cin >> start >> dest;
 
    shortestDistance = getShortestDistance();
    vector<int> path = { dest };
 
    while (1)
    {
        int temp = 0;
 
        if (!path.empty())
        {
            temp = path.back();
        }
 
        path.push_back(shortestParent[temp]);
 
        if (temp == start) break;
    }
 
    path.pop_back();
 
    cout << dist[dest] << endl;
    cout << path.size() << endl;
 
    for (int i = path.size() - 1; i >= 0; --i)
    {
        cout << path[i] << ' ';
    }
}

 

특정 출발지에서 목적지까지의 최소비용 뿐만 아니라 거치는 정점까지 알아내야하는 문제이다.

처음엔 최소비용을 다익스트라로 구한 후에 백트래킹으로 경로를 스택에 넣어놨다가, 목표노드에 도달했을때 최소비용까지 같으면 해당 스택에 담겨있는 경로를 출력해주는 식으로 했다.

 

다만, 답은 구해지기는 하겠지만 바로 시간초과가 발생했다. 

백트래킹에 소모되는 시간때문에 발생한 것 같다.

그래서 다른사람들의 풀이를 보며 다익스트라에서 새로 값을 업데이트해줄 때(pq에 푸쉬해줄 때) 부모와 자식을 설정해주면 된다는걸 알게됐다.

dist에 새로 값을 업데이트해주는 순간은, 그때 기준으로 최단거리를 업데이트해준다는게 보장되어지기 때문이다.

즉, 그때의 curNode와 nextNode는 최단거리로 이어져있다는게 보장되어진다.

 

 shortestParent[nextNode] = curNode;   <-- nextNode의 최단거리 부모노드는 curNode라는것을 의미한다.

 

그러면 끝이다. 다익스트라 한번 돌리면 shortestParent에는 각 노드의 최단거리 부모가 업데이트 되어있을 것이다.

그거를 역으로 출력해주면 된다.

 

 

그리고 위의 코드를 백준의 테스트케이스에 적용하면 1,3,5가 아니라 1,4,5가 나오는데 그래도 상관없다.

단순히 순서의 차이일뿐이다. 실제로 제출해도 통과한다.