[프로그래머스] 가장 먼 노드

문제

https://programmers.co.kr/learn/courses/30/lessons/49189

N개의 노드 중 1번 노드와 가장 먼 거리의 노드수를 구하는 문제

 

문제 풀이

시작점이 정해져있고 최단거리로 이동할 경우 가장 먼 거리를 파악해야 한다.

1번 노드로부터 다익스트라 수행 후 가장 먼 거리를 가진 노드들의 수를 카운트하여 return 한다.

 

소스 코드

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

const int MAX_N = 20001;
const int MAX_M = 50000;

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    
    vector<int> adj[MAX_N];
    int d[MAX_N];
    int answer = 0;
    int maxDist = -1;
    
    // 인접리스트 
    for(int i = 0; i < edge.size(); i++){
        
        int from = edge[i][0], to = edge[i][1];
        adj[from].push_back(to);
        adj[to].push_back(from);
    }
    
    // 초기화
    for(int i = 2; i <= n; i++)
        d[i] = MAX_M + 1;
    
    // 다익스트라
    priority_queue<pair<int,int>> q;
    q.push({0,1});
    
    while(!q.empty()){
        
        int curNode = q.top().second;
        int curDist = -q.top().first;
        q.pop();
        
        if(d[curNode] < curDist) continue;
        
        for(int i = 0; i < adj[curNode].size(); i++){
            
            int nextNode = adj[curNode][i];
            
            if(d[nextNode] <= d[curNode] + 1) continue;
            
            d[nextNode] = d[curNode] + 1;
            // 가장 먼 거리
            maxDist = maxDist < d[nextNode] ? d[nextNode] : maxDist;
            q.push({-(d[nextNode]), nextNode});
        }
    }
    
    for(int i = 1; i <= n; i++)
        if(d[i] == maxDist) answer++;
    
    return answer;
}