1916번

1916번 - 최소 비용 구하기

문제를 그래프 모델로 바꾸고, 주어진 시작점과 끝점에서의 최단 거리를 구하면 된다.

가중치가 있고, 최단거리를 구하기 때문에 bfs 가 아닌 다익스트라 알고리즘을 사용하면 된다.

다익스트라 알고리즘은 두가지 방식으로 풀 수 있는데,

첫번째는 우선 순위 큐를 이용하는 방법으로 O(ElogV) 의 시간복잡도,

두번째는 우선 순위 큐를 이용하지 않는 방법으로 O(VE)의 시간복잡도( 연결리스트로 풀 경우).

나는 우선 순위 큐를 이용해서 문제를 풀었다.

다익스트라로 풀어보는 첫 문제라서, 우선 순위 큐를 쓸때랑, 쓰지 않을 때 방법이 자꾸 섞여서 생각났다.

더 풀어보면서 확실히 다익스트라를 두가지 방식으로 푸는걸 잡아야겠다.

우선 순위 큐로 풀 때는, 방문을 확인하는 배열이 따로 필요가 없다. 대신 똑같은 곳을 방문하게 될 때, 기존 값과 새로운 값을 

비교해주기만 하면 된다. 나머지는 BFS 와 굉장히 유사

##priority queue 를 사용하지 않는 다익스트라 추가

<정답 코드 - priority queue 사용>

#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
const int INF = 987654321;
int n, m, start, dest;
 
int main()
{
 
    scanf("%d %d", &n,&m);
 
    vector < vector<pair<int, int>>> v(n + 1);
    vector<int> dist(n + 1);
 
    for (int i = 1; i <= n; i++)
    {
        dist[i] = INF;
    }
 
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        v[a].push_back({ b,c });
    }
 
    scanf("%d %d", &start, &dest);
 
    priority_queue<pair<int, int>> pq;
    pq.push({ start,0 });
    dist[start] = 0;
 
 
    while (!pq.empty())
    {
        int now = pq.top().first;
        int cost = -pq.top().second;
        pq.pop();
 
        if (dist[now] < cost) 
        {
            continue;
        }
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i].first;
            int w = v[now][i].second;
 
            if (dist[now]!=INF && dist[next] > dist[now] + w)
            {
                dist[next] = dist[now] + w;
                pq.push({ next,-dist[next] });
            }
        }
        
    }
 
    printf("%d\n", dist[dest]);
 
    return 0;
 
}

<정답 코드 - priority queue 쓰지 않음 >

#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
const int INF = 987654321;
int n, m, start, dest;
 
int main()
{
 
    scanf("%d %d", &n,&m);
 
    vector < vector<pair<int, int>>> v(n + 1);
    vector<int> dist(n + 1);
    vector<bool> visited(n + 1);
 
    for (int i = 1; i <= n; i++)
    {
        dist[i] = INF;
        visited[i] = false;
    }
 
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        v[a].push_back({ b,c });
    }
 
    scanf("%d %d", &start, &dest);
 
    dist[start] = 0;
 
    while (true)
    {
        int now;
        int distance = INF;
        for (int i = 1; i <= n; i++)
        {
            if (!visited[i] && distance > dist[i] && dist[i] != INF)
            {
                distance = dist[i];
                now = i;
            }
        }
 
        if (distance == INF)
        {
            break;
        }
 
        visited[now] = true;
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i].first;
            int cost = v[now][i].second;
 
            if (dist[next] > dist[now] + cost)
            {
                dist[next] = dist[now] + cost;
            }
        }
 
    }
 
    printf("%d\n", dist[dest]);
 
    return 0;
 
}