[BOJ, C++]#5972_택배 배송, 다익스트라, 길 찾기 알고리즘, 최단 경로 알고리즘, 무 방향 그래프

#1. 문제

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

 

---

 

#2. 풀이

 

1. 다익스트라

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

다익스트라 알고리즘은 단일-출발 최단 경로 알고리즘으로, 그래프 내 어떤 출발 정점으로부터 다른 모든 정점에 대하여 최단 경로 값을 찾는 알고리즘입니다. 다익스트라 알고리즘은 양수 가중치를 가지며, 순환 구조가 없는 그래프에서 활용 가능한 '단일-출발' 혹은 '단일-쌍' 최단 경로 알고리즘입니다.

 

2. 단일-출발 최단 경로 알고리즘 통해 최단 경로 찾기!

1. 먼저, vector <vector <pair <int, int>>> 형식의 컨테이너를 통해 그래프를 먼저 구성합니다. 이때, 간선의 방향성이 없는 무방향성 그래프이므로, a->b와 더불어 b->a 간선에 대한 정보도 같이 저장해 줍니다.
2. 다음으로, 다익스트라 알고리즘을 구현합니다. 다익스트라 알고리즘은 우선순위 큐(최소 힙), 방문 여부 체크(무방향성 그래프 중복 방문 방지), 최단 경로 값(INT_MAX로 초기화)을 활용하여 출발 정점으로부터 다른 모든 정점에 대하여 최단 경로 값을 찾습니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/5972
*   @문제: 양방향 그래프에서 1번 정점에서 N번 정점으로 가는 최단 경로의 가중치의 합
*   @설명
        1. 무방향 그래프, '방문 여부' 체크
        2. 가중치가 서로 다르기 때문에, BFS는 못씀
        3. 다익스트라 활용 적절(단일 출발)
*/


#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
using namespace std;

#define MAX 50001
typedef pair<int,int> p;

int N, M;
vector<vector<p>> graph;

void dijkstra(int start)
{
    //@최소 힙, 우선순위 큐
    priority_queue<p, vector<p>, greater<p>> pq;
    //@방문 여부, 무방향 그래프
    vector<bool> visited(N+1, false);
    //@최단 경로 목록
    vector<int> dist(N+1, INT_MAX);

    //@출발 정점
    pq.push({0, start});
    dist[start] = 0;

    //@다익스트라
    while(!pq.empty())
    {
        //@최단 경로 값을 갖는 정점 
        int curDist = pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        //@방문 여부 체크
        if(visited[cur]) continue;

        visited[cur] = true;

        for(const auto edge : graph[cur])
        {
            int next = edge.first;
            int newDist = curDist + edge.second;
            //@최단 경로 업데이트 여부
            if(newDist < dist[next])
            {
                dist[next] = newDist;
                pq.push({newDist, next});
            }
        }
    }

    //@결과 출력
    cout << dist[N];

}

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

    cin >> N >> M;

    //@resize
    graph.resize(N+1);

    while(M--)
    {
        int a,b,c;

        cin >> a >> b >> c;

        graph[a].push_back({b,c});
        graph[b].push_back({a,c});
    }
    //@다익스트라 호출(단일 출발, 출발 정점: 1)
    dijkstra(1);

    return 0;
}

 

---