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

1.문제 링크

가장 먼 노드

2. 풀이 전 계획과 생각

• 다익스트라 알고리즘 사용

3. 풀이

#include <string>
#include <vector>
#include<queue>
#define INF 1e9
using namespace std;

vector<int> graph[20001];
int dist[20001];

void dijkstra(int start){
    priority_queue<pair<int , int>> pq;
    pq.push({0,start});
    dist[start]=0;

    while(!pq.empty()){
        int d = pq.top().first;
        int now = pq.top().second;
        pq.pop();

        if(dist[now]<d) continue;
        for(int i=0;i<graph[now].size();i++){
            int cost = d + 1;
            if(cost< dist[graph[now][i]]){
                dist[graph[now][i]] = cost;
                pq.push({cost, graph[now][i]});
            }
        }
    }
}

int solution(int n, vector<vector<int>> edge) {

    fill(dist, dist+n+1, INF);

    for(int i=0;i<edge.size();i++){
        graph[edge[i][0]].push_back(edge[i][1]);
        graph[edge[i][1]].push_back(edge[i][0]);
    }

    dijkstra(1);

    int answer = 0;
    int best=-1;
    for(int i=1;i<=n;i++){
        if(dist[i]>best) best=dist[i];
    }
    for(int i=0;i<=n;i++){
        if(dist[i]==best) answer++;
    }
    return answer;
}

다익스트라 알고리즘을 통해 1번 노드에서 각 노드의 최단 거리를 구한다. 각 노드간에 비용은 1이다.

1번 노드에서 각 노드로 가는 최단 거리 중 최대값을 구한 후, 그 최댓값의 개수를 구해 반환한다.

4. 풀이하면서 고민했던 점

5. 문제를 풀고 알게된 개념 및 소감

• 다익스트라 알고리즘을 복습할 수 있었음