[BOJ] 1719번 :택배(C++)

문제 링크 : 백준 1719번

[문제 접근]

기본적인 풀이는 다익스트라로 풀었는데 가장 먼저 거쳐야하는 집하장을 찾아야하므로 최단 경로를 거쳐가는 경로들을 저장해주어야 한다.

나는 ans배열에 저장했는데 ans[next] = cur 이라는 뜻은 next에 오기 전 경로는 cur이라는 뜻이다.
ex) ans[2] = 1 는 1에서 2의 경로로 진행했다는 뜻

1. arr백터에 정보들을 저장한다.
2. 다익스트라 함수로 들어간다.
3. 큐의 우선순위를 오름차순으로 설정한다.
4. 최단 경로를 탐색하면서 ans배열에 전 경로를 저장해준다.
5. 최단 경로 탐색이 끝나면 정답을 출력해야한다.
   • 현재 집하장(i)과 탐색 시작점(num)이 같으면 자기 자신이므로 -를 출력한다.
   • 현재 집하장의 전 경로(ans[i])가 탐색 시작점(num)과 같으면 현재 집하장을 출력한다.
   • 그 외의 경우에는 집하장의 전 경로가 탐색 시작점과 같은 경우가 나올 때까지 집하장을 거슬러올라간다.

[소스 코드]

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

using namespace std;
int n, m;
typedef pair<int, int> p;
vector<p> arr[201];
int dir[201];
int ans[201];

void dijsktra(int num) {
    memset(dir, 200000, sizeof(dir));
    dir[num] = 0;
    priority_queue<p, vector<p>, greater<p>> pq;
    pq.push({0, num});
    while(!pq.empty()) {
        int cur = pq.top().second;
        pq.pop();

        for(int i=0 ; i<arr[cur].size() ; i++) {
            int next = arr[cur][i].first;
            if(dir[next]>dir[cur]+arr[cur][i].second) {
                ans[next] = cur; // 경로를 저장
                dir[next] = dir[cur]+arr[cur][i].second;
                pq.push({dir[next], next});
            }
        }
    }

    for(int i=1 ; i<=n ; i++) {
        if(i==num) { // 현재 집하장과 탐색 시작점이 같으면 자기 자신이므로 - 출력
            cout << "- ";
        } else if(ans[i]==num) { // 현재 집하장의 전 경로(ans[i])가 탐색 시작점과 같으면 해당 집하장 출력
            cout << i << " ";
        } else { // 그 외의 경우
            int now = i;
            while(true) {
                if(ans[now]==num) {
                    cout << now << " ";
                    break;
                } else {
                    now = ans[now]; // 전 경로로 거슬러 올라감
                }
            }
        }
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i=0 ; i<m ; i++) {
        int u,v,a;
        cin >> u >> v >> a;
        arr[u].push_back({v, a});
        arr[v].push_back({u, a});
    }
    for(int i=1 ; i<=n ; i++) {
        dijsktra(i);
    }

    return 0;
}