[프로그래머스 level 3] 가장 먼 노드 (C++)

다익스트라 문제

시작노드는 1번으로 고정되어 있고, 간선 사이의 거리는 항상 1로 고정되어 있다.

 

일반적인 다익스트라 풀이와 거의 동일하다.

하지만 1번 노드에서 가장 멀리 떨어진 노드의 거리가 최댓값으로 갱신될 때마다 답을 1로 초기화 시켜야 한다.

 

ex

우선순위 큐에 1번 노드가 있다.

가장 먼저 2번 노드에 방문하면 1번 노드와의 최대 거리가 1로 갱신이 되고, 가장 멀리 떨어진 노드의 수는 1이 된다.

그리고 3번 노드에 방문하면 1번 노드와의 거리가 1이므로 현재 최댓값인 1과 동일하다. 따라서 가장 멀리 떨어진 노드의 수는 2로 갱신이 된다.

동일한 방법으로 4, 5, 6번 노드에 방문하면 최대 거리가 2로 갱신이 되고, 가장 멀리 떨어진 노드의 수는 3이 될 것이다.

 

 

최종 코드

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

#define pii pair<int, int>
#define INF 1e9+7

using namespace std;

vector<int> adj[20001];
int dist[20001];
int max_far, ans;

void dijkstra(){
    priority_queue<pii, vector<pii >, greater<pii > > pq;
    pq.push({0, 1});
    
    dist[1] = 0;
    
    while(!pq.empty()){
        int now = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
        
        if(cost > dist[now]) continue;
        if(cost == max_far) ans++;
        else if(cost > max_far){
            max_far = cost;
            ans = 1;
        }
        
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i];
            int next_cost = cost + 1;
            
            if(next_cost < dist[next]){
                dist[next] = next_cost;
                pq.push({next_cost, next});
            }
        }
    }
}

int solution(int n, vector<vector<int>> edge) {
    
    for(auto ed: edge){
        adj[ed[0]].push_back(ed[1]);
        adj[ed[1]].push_back(ed[0]);
    }
    for(int i = 1; i <= n; i++){
        dist[i] = INF;
    }
    
    dijkstra();
    
    return ans;
}