백준 1753번 최단경로

문제 링크입니다: https://www.acmicpc.net/problem/1753

작년 자료구조 시간에 배운 다익스트라(Dijkstra) 알고리즘을 복습하기 위해 풀어본 문제였습니다.

다익스트라 알고리즘은 시작점을 기준으로 인접한 노드들을 방문하며 시작점에서 해당 노드까지의 최소 거리를 찾는 알고리즘입니다.

인접한 노드들을 방문한 뒤에는 인접한 노드들의 인접한 노드들을 확인하는 방식으로 작동합니다.

한가지 주의할 점은 인접한 노드들을 방문할 때 비용이 최소인 노드부터 방문하므로 우선순위 큐에 비용을 음수 처리하여 넣어야한다는 점입니다.

Priority Queue는 기본적으로 값의 크기대로 우선순위를 부여하기 때문에 위와 같이 처리해야합니다.

물론, 우선순위 큐를 선언할 때 원하는 규칙을 설정해준다면 보다 직관적인 코드를 작성할 수 있습니다.

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

 

const int MAX = 20000 + 1;

const int INF = 987654321;

 

int V, E, K;

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

 

vector<int> dijkstra(int start, int vertex)

{

        vector<int> distance(vertex, INF); //start를 기준으로 거리

        distance[start] = 0; //자기 자신한테 가는 비용 0

 

        priority_queue<pair<int, int>> pq; //Cost, Vertex

        pq.push(make_pair(0, start)); //초기 비용과 시작점

 

        while (!pq.empty())

        {

                 int cost = -pq.top().first; //거리의 부호를 바꾸어 거리가 작은 정점부터 꺼내지게 하였으므로 부호를 바꿔준다

                 int curVertex = pq.top().second;

                 pq.pop();

                

                 //최소거리를 원하므로

                 if (distance[curVertex] < cost)

                         continue;

 

                 //neighbor 다 확인

                 for (int i = 0; i < graph[curVertex].size(); i++)

                 {

                         int neighbor = graph[curVertex][i].first;

                         int neighborDistance = cost + graph[curVertex][i].second;

 

                         //최소 경로 발견시 업데이트

                         if (distance[neighbor] > neighborDistance)

                         {

                                 distance[neighbor] = neighborDistance;

                                 //거리의 부호를 바꾸어 거리가 작은 정점부터 꺼내지도록하기 위해

                                 pq.push(make_pair(-neighborDistance, neighbor));

                         }

                 }

        }

        return distance;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> V >> E >> K;

 

        V++; //정점번호 1부터 시작

 

        for (int i = 0; i < E; i++)

        {

                 int source, destination, cost;

                 cin >> source >> destination >> cost;

 

                 graph[source].push_back(make_pair(destination, cost));

        }

 

        vector<int> result = dijkstra(K, V);

 

        for (int i = 1; i < V; i++)

        {

                 if (result[i] == INF)

                         cout << "INF\n";

                 else

                         cout << result[i] << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~