[Programmers/C++] 가장 먼 노드

시간 복잡도

• 다익스트라 알고리즘을 사용하여 최단 경로를 구하면 $O(ElogV)$의 시간 복잡도가 발생합니다,
• 추가적으로 최단 거리 배열을 순회하며 최대 거리와 동일한 값을 찾아야 하기 때문에 $O(n)$의 시간이 추가로 발생합니다.

문제 접근법

• 도착 지점과 가중치로 이루어진 그래프를 인접 행렬로 구현합니다.
• 간선이 양방향이기 때문에 그래프를 인접 행렬로 구현 시 양방향 모두 연결해주어야 합니다.
• 다익스트라 알고리즘으로 시작 노드부터 모든 노드간의 최단 거리를 계산합니다.
• 최단 거리 배열을 순회하며 최단 거리의 최댓값과 같은 노드의 개수를 카운트합니다.

코드

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

using namespace std;

using Node = pair<int, int>;

static vector<vector<Node>> G;
static vector<int> dist;
static int maxDist=0;

void djikstra(int node)
{
    priority_queue<Node, vector<Node>, greater<>> pq;
    pq.push({0, node});
    
    dist[node]=0;
    
    while(!pq.empty())
    {
        Node now = pq.top();
        pq.pop();
        
        int nowNode = now.second;
        int nowDist = now.first;
        
        if(nowDist > dist[nowNode])
            continue;
        
        for(Node next : G[nowNode])
        {
            int nextNode = next.first;
            int weight = next.second;
            
            if(dist[nextNode] > dist[nowNode] + weight)
            {
                dist[nextNode] = dist[nowNode] + weight;
                pq.push({dist[nextNode], nextNode});
                maxDist = max(dist[nextNode], maxDist);

            }
        }
        
    }
    
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    G.resize(n+1);
    dist.resize(n+1, INT_MAX);
    
    for(vector<int> v : edge)
    {
        G[v[0]].emplace_back(v[1], 1);
        G[v[1]].emplace_back(v[0], 1);
    }
    
    djikstra(1);
    

    
    for(int i=1; i<=n; i++)
    {
        if(dist[i] == maxDist)
            answer++;
    }
    
    return answer;
}