[프로그래머스] 가장 먼 노드 / 최단 경로, 다익스트라

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

 

💣 문제 이해

 

 

한 출발 정점에서 다른 모든 정점으로의 최단 경로 이동 비용을 계산하는 문제였다.

각 노드로 이동하는 최소 비용을 계산하여 그중 최대를 구한 후,

동일한 비용을 지불하는 경로의 수를 카운트 했다.

 

이 문제는 다익스트라 알고리즘으로 풀이했다.

 

 

💭 풀이 과정

 

 

 

작성 언어: C++

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

const int MAX = 20001;
const int INF = 1e9;
int dist[MAX] = {0, };


int solution(int n, vector<vector<int>> edge) {
    int max_cost = 0;
    int result = 0;
    priority_queue<pair<int, int>>pq;   // 비용, 노드번호
    vector<int>nodes[n+1];
    // 각 노드까지 도달하는데 최소 비용(큰 값으로 설정)
    fill_n(dist, MAX, INF);
    // 노드 기준으로 연결되어 있는 노드들의 정보를 표기
    for (int i = 0; i < edge.size(); ++i) {
        int vertex_a = edge[i][0];
        int vertex_b = edge[i][1];
        nodes[vertex_a].push_back(vertex_b);
        nodes[vertex_b].push_back(vertex_a);
    }
    
    pq.push({0, 1});
    // 우선순위 큐 내에서 가장 작은 값을 먼저 반환할 것.
    // 우선순위 큐는 최대 힙을 사용하므로 cost를 음수화해서 최소 힙으로 사용.
    while (!pq.empty()) {
        int cur_cost = pq.top().first * -1;
        int cur_node = pq.top().second;
        pq.pop();
        
        for (int i = 0; i < nodes[cur_node].size(); ++i) {
            int next_node = nodes[cur_node][i];
            
            if (dist[next_node] <= cur_cost + 1) continue;
            
            dist[next_node] = cur_cost + 1;
            pq.push({dist[next_node]*-1, next_node});
        }
    }
    
    max_cost = *max_element(dist+2, dist+n);
    for (int i = 2; i <= n; ++i) {
        if (dist[i] == max_cost)    result++;
    }
    return result;
}

 

다익스트라 알고리즘에서

정점 개수가 V이고 간선 갯수가 E일 때 일반적인 방식으로는 시간 복잡도가 O(V^2)가 되며,

우선순위 큐를 사용한다면 Heap을 사용하여 시간복잡도가 O(ElogV)가 된다.

즉, 노드의 수가 많아지면 많아질수록, 우선순위 큐를 사용하는 것이 매우 효과적이다.