BOJ_1719

😄 다익스트라로 풀어냈는데, 경로를 저장해야하는 점에서 기존의 문제와 다른 것 같다.

1719번: 택배

• 다익스트라 알고리즘으로 각 노드사이의 최소 거리를 찾음과 동시에 거쳐간 노드를 저장해줘야 최단거리 중 가장 처음에 갔던 노드를 뽑아낼 수 있다.
• 일단 일반 다익스트라 알고리즘에서 path에 전에 거쳐간 노드를 저장해준다.

💻 다익스트라 알고리즘

void bfs(int node)
{
    vector<int> dist(n + 1, 987654321);
    priority_queue<pair<int, int> > q;
    q.push(make_pair(node, 0));
    dist[node] = 0;
    while(!q.empty())
    {
        int cur = q.top().first;
        int cost = -q.top().second;
        q.pop();
        if(cost > dist[cur])
            continue;
        for (int i = 0; i < v[cur].size(); i++)
        {
            int next = v[cur][i].first;
            int ncost = v[cur][i].second;
            if(dist[next] > cost + ncost)
            {
                dist[next] = cost + ncost;
                q.push(make_pair(next, -dist[next]));
                path[next] = cur;
            }
        }
    }
    for (int i = 1; i <= n;i++)
    {
        if(node == i)
            ans[node][i] = "-";
        else{
            int t = i;
            while (path[t] != node)
            {
                t = path[t];
            }
            ans[node][i] = to_string(t);
        }
    }
}

• 위의 코드는 일반적인 다익스트라 알고리즘이다. 여기서 path 배열을 추가해 최소거리로 갱신될 때마다, 그 전에 거쳐갔던 노드를 저장해준다.
• 후에 for문을 통해 자신이 거쳐간 path를 시작 노드가 나올때까지 while을 돌려주고 답이 나오면 이를 ans값에 저장해준다.

💻전체코드

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

using namespace std;

#define endl "\n"

vector<pair<int,int> > v[201];
int path[201];
string ans[201][201];
int n, m;

void bfs(int node)
{
    vector<int> dist(n + 1, 987654321);
    priority_queue<pair<int, int> > q;
    q.push(make_pair(node, 0));
    dist[node] = 0;
    while(!q.empty())
    {
        int cur = q.top().first;
        int cost = -q.top().second;
        q.pop();
        if(cost > dist[cur])
            continue;
        for (int i = 0; i < v[cur].size(); i++)
        {
            int next = v[cur][i].first;
            int ncost = v[cur][i].second;
            if(dist[next] > cost + ncost)
            {
                dist[next] = cost + ncost;
                q.push(make_pair(next, -dist[next]));
                path[next] = cur;
            }
        }
    }
    for (int i = 1; i <= n;i++)
    {
        if(node == i)
            ans[node][i] = "-";
        else{
            int t = i;
            while (path[t] != node)
            {
                t = path[t];
            }
            ans[node][i] = to_string(t);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < m;i++)
    {
        int a, b, dis;
        cin >> a >> b >> dis;
        v[a].push_back(make_pair(b,dis));
        v[b].push_back(make_pair(a, dis));
    }

    for (int i = 1; i <= n;i++)
    {
        bfs(i);
    }
    for (int i = 1; i <= n;i++)
    {
        for (int j = 1; j <= n;j++)
            cout << ans[i][j] << " ";
        cout << endl;
    }
}

경로를 저장하는 부분에서 조금 막혀서 검색을 통해 풀어냈다..😭 경로 저장도 대충 연쇄적으로 이루어진다는 점을 알았다.