[프로그래머스/고득점 Kit/깊이/그래프] 가장 먼 노드

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

코딩테스트 연습 - 가장 먼 노드

 

난이도

최단거리 / 난이도 ⭐️⭐️⭐️/ 1.5시간 

 

문제풀이

최단거리  문제이다. 다익스트라 알고리즘을 알고있으면 쉽게 풀 수 있으나, 몰라서 오래걸렸다.

 

#include <string>
#include <vector>
#include <queue>
#include <utility>
#include <iostream>
#define INF 1000000000
using namespace std;


int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    vector<vector<int> > vertex(n+1, vector<int>());
    for(int i=0; i<edge.size(); i++){
        vertex[edge[i][0]].push_back(edge[i][1]);
        vertex[edge[i][1]].push_back(edge[i][0]);
    }
    
    vector<int> d(n+1, INF);
    d[1] = 0;
    
    priority_queue<pair<int, int> > pq;
    pq.push({0, 1}); // cost index
    
    int cur;
    int cost;
    int next;
    int ncost;
    while(!pq.empty()){
        cost = -pq.top().first;
        cur = pq.top().second;
        pq.pop();
        
        if(d[cur] < cost)
            continue;
        
        for(int i=0; i<vertex[cur].size(); i++){
            next = vertex[cur][i];
            ncost = cost + 1;
            
            if(ncost < d[next]){
                d[next] = ncost;
                pq.push({-d[next], next});
            }    
        }
    }
    
    int max = d[1];
    int max_cnt = 1;
    for(int i=2; i<d.size(); i++){
        if(max < d[i]){
            max = d[i];
            max_cnt = 1;
        }else if(max == d[i]){
            max_cnt += 1;
        }
    }
    
    answer = max_cnt;
    
    return answer;
}