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

문제 주소

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

 

풀이

단방향 간선이 아니라 양방향 간선으로 unordered_map에 입력해야 한다!

단방향 간선으로 입력해서 다 틀린 거였다....

그 다음은 그냥 다익스트라 최단 거리 알고리즘 사용한 후에 가장 먼 노드의 개수 구하면 된다.

 

코드

#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <set>

using namespace std;
#define INF 1e9

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    // 이어진 노드를 기록
    unordered_map<int, set<int>> m;
    
    for (auto e : edge){
        m[e[0]].insert(e[1]);
        m[e[1]].insert(e[0]);
    }
    
    priority_queue<pair<int, int>> pq;
    vector<int> dist(n+1, INF); // 최단 거리 기록
    dist[1] = 0; // 시작 노드의 거리 초기화
    pq.push({0, 1}); // 시작 노드 입력
    
    while(!pq.empty()){
        // 최소 힙으로 동작하게 하기 위해 음수로 만든다
        int cur_dist = -pq.top().first;
        int cur_node = pq.top().second;
        pq.pop();
        
        for (auto nxt_node : m[cur_node]){
            if (dist[nxt_node] > cur_dist+1){
                dist[nxt_node] = cur_dist+1;
                pq.push({-(cur_dist+1), nxt_node});
            }
        }
    }
    
    // 가장 멀리 떨어진 노드 개수 세기
    int max = 0;
    for (int i = 1; i <= n ; i++){
        if (max < dist[i]){
            max = dist[i];
            answer = 1;
        }
        else if (max == dist[i]){
            answer++;
        }
    }
    
    return answer;
}