Beakjoon 1753 최단경로

26 Feb 2021 in Algorithm

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

나의 풀이

이 문제는 다익스트라 알고리즘을 이용하여 문제를 해결할 수 있다.

먼저 위와 그래프가 위와 같을 때 A에서 모든 정점까지의 최단거리를 구해보자

A를 방문했을 때 A에서 모든 정점까지의 최단거리를 표로 나타내었다. 먼저 A에서 A로 가는 거리는 자기 자신이기 때문에 0으로 초기화하였고, B와 D는 가중치 값에 따라 각각 10, 3이 된다. 또한 C와 E는 현재 A에서 두 정점을 방문할 수 없기 때문에 무한대를 의미하는 INF로 표현하였다.
다음으로 방문할 수 있는 가장 가까운 정점을 확인한다. 현재 D가 거리 3으로 가장 가깝기 때문에 D를 방문한다.

D에서 방문할 수 있는 정점을 확인해 보면 정점 B가 존재한다. 때문에 A에서 B로 방문하는 경우의 수가 증가하였고, 이 경우가 A에서 B로 가는 최단 경로가 될 수 있기 때문에 기존에 최단거리라고 생각했던 표에서 B의 거리 값과 (A에서 D까지 갈 수 있는 최단거리 + D에서 B까지의 거리)를 비교하여 더 가까운 거리로 표를 업데이트한다. 위 경우에서는 기존 B의 거리 = 10, (A에서 D까지 갈 수 있는 최단거리 + D에서 B까지의 거리) = 3+2 = 5이기 때문에 거리를 5로 업데이트한다. 다음으로 방문할 수 있는 가장 가까운 정점은 B이기 때문에 정점 B를 방문한다.

마찬가지로 B에서 방문할 수 있는 정점인 E까지의 거리를 기존 거리와 B를 통해 갈 수 있는 경로와 비교한다. 기존 E까지 거리 = INF, B를 통해 E까지 가는 최단거리 = 5+6 = 11이기 때문에 A에서 E까지의 최단거리를 업데이트 한다.

같은 방법으로 E를 방문하면 다음으로 방문할 수 있는 정점이 없기 때문에 종료하고 최종적으로 A에서 모든 정점까지의 최단거리를 구할 수 있다.

위 과정에서 다음으로 방문할 수 있는 가장 가까운 정점을 확인할 때 시간복잡도를 줄이기 위해 Proirity queue를 사용하였다.

풀이 코드 : 1753 최단경로

#include <iostream>
#include <vector>
#include <queue>

#define INF 2147483647

using namespace std;

struct edge{
    int next;
    int weight;
};
vector<int> dist;
vector<int> visit;
vector<vector<edge>> graph;

void dijkstra(int start){
    priority_queue<pair<int,int>> pq;
    dist[start] = 0;
    pq.push(make_pair(0, start));
    int curr;
    while(!pq.empty()){
        curr = pq.top().second;
        pq.pop();
        
        if(visit[curr] == 1) continue;

        for(int i=0;i<graph[curr].size();i++){
            int next = graph[curr][i].next;
            int w = graph[curr][i].weight;

            if(visit[next] != 1 && dist[next] > dist[curr] + w){
                dist[next] = dist[curr] + w;
                pq.push(make_pair(-dist[next], next));
            }
        }
    }
}

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

    int V, E, K;
    cin>>V>>E;
    cin>>K;

    graph.resize(V+1);
    dist.resize(V+1);
    visit.resize(V+1);

    int u, v, w;
    for(int i=1;i<=E;i++){
        cin>>u>>v>>w;
        edge e;
        e.next = v;
        e.weight = w;
        graph[u].push_back(e);
    }    

    for(int i=1;i<=V;i++){
        dist[i] = INF;
    }

    dijkstra(K);

    for(int i=1;i<=V;i++){
        if(dist[i] == INF)
            cout<<"INF\n";
        else
            cout<<dist[i]<<"\n";
    }
}

채점결과