[백준/Baekjoon] 11779 최소비용 구하기 2 C++ :: Graph / Dijkstra

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

11779번: 최소비용 구하기 2

---

1. Logic

- 모든 버스 비용이 0보다 크거나 같다고 나왔기 때문에 다익스트라 알고리즘을 사용하여 풀이한다는 것을 유추할 수 있다.

 

일반 다익스트라 알고리즘과 동일하게 풀이하지만 해당 문제는 지나온 경로까지 표현해줘야 하기 때문에 경로를 추적하는 trace 배열을 한개 더 선언해주었다.

 

trace배열로 경로를 찾는 과정

문제의 Testcase에서 내가 도출한 정답의 경로는 1 - 4 - 5로 총 cost는 4이다.

 

1번 노드에서 갈 수 있는 경로의 수는 2, 3, 4, 5로 5개지만 그중 최단경로는 4번으로 가는 경우이기 때문에 Trace[4] = 1이 된다. 그후 4에서 5로 가는 최단거리는 1로 Trace[5] = 4가 된다.

 

목표 노드 End에 도착하기 전에 왔던 노드 Trace[5]를 확인해보니 4

4번째 노드를 도착하기 전에 왔던 노드 Trace[4]를 확인해보니 1

Start는 1번째 노드에서 시작했기 때문에 추적 완료

 

 

모든 경우의 수에서 추적하기위한 경로를 갱신해주면 최단거리의 경로가 안나오기 때문에 최단거리를 갱신하는 경우에만 지나온 Trace배열에 값을 갱신해 주었다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int n, m;
int Start, End;

vector<pair<int, int>> vec[1001];
vector<int> dist(1001, INF);
vector<int> tra;
int trace[1001];

void dijkstra() {
    priority_queue<pair<int, int>> pq;

    dist[Start] = 0;
    pq.push({Start, 0});

    while(!pq.empty()) {
        int cur = pq.top().first;
        int cost = -pq.top().second;
        pq.pop();

        if(cost > dist[cur]) continue;

        for(int i = 0; i < vec[cur].size(); i++) {
            int next = vec[cur][i].first;
            int ncost = vec[cur][i].second;
            
            if(dist[next] > cost + ncost) {
                trace[next] = cur;
                dist[next] = cost + ncost;
                pq.push({next, -dist[next]});
            }
        }
    }

    cout << dist[End] << "\n";
    
    int check = End;
    while(true) {
        if(check == Start) {
            tra.push_back(Start);
            break;
        }
        tra.push_back(check);
        check = trace[check];
    }

    cout << tra.size() << "\n";

    for(int i = tra.size() - 1; i >= 0; i--) {
        cout << tra[i] << " ";
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;

    for(int i = 0; i < m; i++) {
        int s, e, c;
        cin >> s >> e >> c;

        vec[s].push_back({e, c});
    }

    cin >> Start >> End;

    dijkstra();
}

 

 

---

 

 

3. Feedback

- 로직을 다 구성하고 제출했더니 계속해서 시간초과가 났다. 알고보니 큐에서 값을 체크하면서부터 값을 확인하여 답이 되지 못할 경우의 수는 일찌감치 제외시켜줘야 하는 조건이 들어가있어서 계속해서 시간초과가 발생했다.

 

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐