[BOJ알고리즘, C++]#1446_지름길, 최단 경로, 길 찾기, 다익스트라

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. 다익스트라

[알고리즘]#2_길 찾기 알고리즘

다익스트라 알고리즘은 '단일-출발' 최단 경로 알고리즘입니다. 시작 정점을 기준으로 다른 모든 정점에 대하여 최단 경로 값을 찾는 알고리즘으로, 일반적으로 우선순위 큐와 BFS를 활용합니다.

 

2. 유방향 그래프에 대한 다익스트라 알고리즘!

1. 먼저, 유방향 그래프를 구성합니다. 지름길 외에도 각 지점마다 '지름길'이 아닌 일반 길에 대한 경로도 추가해주어야 합니다.
2. 다음으로, 0을 출발 정점으로 설정한 다익스트라를 수행합니다. '유방향' 그래프에 대한 다익스트라의 경우 '방문 여부' 대신 현재 최단 경로 값이 현재 정점의 최단 경로 값보다 작을 경우에만 수행할 수 있도록 작성합니다.

 

---

 

#3. 코드

/*
<<<<<<< HEAD
    @문제 : 유방향 그래프, 
=======
    @문제 : 주어진 지름길 목록을 통해 도착점 까지의 최단 경로 찾기
    @설명
        1. 다익스트라 활용
        2. 그래프 구성 시 지름길 외 일반 경로에 대한 내용도 추가
>>>>>>> 186a492418d48ecfac2bba86f20016dde3a4a5b2
*/

#include <iostream>
#include <vector>

using namespace std;

#include <queue>
#include <climits>
using namespace std;

#define MAX 10001

int N, D;
vector<pair<int, int>> graph[MAX];

void dijkstra()
{
    // 최단 경로 목록
    vector<int> dist(MAX, INT_MAX);
    // 우선순위 큐, pair< dist, node >
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

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

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

        if (curDist > dist[cur])
            continue;

        for (const auto edge : graph[cur])
        {
            int neighbor = edge.first;
            int weight = edge.second;

            if (neighbor > D)
                continue;

            if (dist[neighbor] > curDist + weight)
            {
                dist[neighbor] = curDist + weight;
                pq.push({dist[neighbor], neighbor});
            }
        }
    }

    cout << dist[D];
}

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

    cin >> N >> D;

    for (int i = 0; i <= D; ++i)
        graph[i].push_back({i + 1, 1});

    while (N--)
    {
        int u, v, w;
        cin >> u >> v >> w;

        // 지름길 : v-u 거리가 w보다 클 때만 지름길이다!
        if (v <= D && v - u > w)
            graph[u].push_back({v, w});
    }

    // 다익스트라
    dijkstra();

    return 0;
}

 

---