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

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

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

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 987654321
using namespace std;

class Node{
    public:
    int id;
    int cost;
    Node(int id, int cost) : id(id), cost(cost)
    {}
};

struct compare{
    bool operator()(Node a, Node b){
        return a.cost>b.cost;
    }
};

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<vector<int>> adjList(n+1);
    int dist[n+1];
    for (int i=2; i<=n; i++){
        dist[i]=MAX;
    }
    for (vector<int> e: edge){
        adjList[e[0]].push_back(e[1]);
        adjList[e[1]].push_back(e[0]);
    }
    priority_queue<Node, vector<Node>, compare> pq;
    dist[0]=0;
    dist[1]=0;
    pq.push(Node(1,0));
    while (!pq.empty()){
        Node now=pq.top();
        pq.pop();
        if (now.cost>dist[now.id]){
            continue;
        }
        for (int i=0; i<adjList[now.id].size(); i++){
            int next=adjList[now.id][i];
            if (dist[next]>now.cost+1){
                dist[next]=now.cost+1;
                pq.push(Node(next,dist[next]));
            }
        }
    }
    int maxVal=*max_element(dist, dist+n+1);
    for (int i=2; i<=n; i++){
        if (dist[i]==maxVal){
            answer++;
        }
    }
    return answer;
}

 

출발점 고정, 최단 거리라서 다익스트라로 풀었다.

거리 배열 dist에서 가장 큰 값을 가지는 애들의 수를 센다.

dist 배열을 MAX로 세팅한 후, 현재 노드+현재 노드와 연결된 이웃 노드의 거리가 dist 배열보다 작을 때 이웃 노드의 dist 배열을 갱신해주는 식이다.

 

bfs로 푸는 방법도 있다.

1번째 노드에서 시작해, 이웃 노드 방문 하면서(미방문 상태인 노드에 한해), dist 배열에 거리값 넣어주고 이웃 노드를 다시 큐에 넣어주면, 최종적으로 dist 배열 안에 1번 노드부터 각 노드까지의 최단거리가 나올 수 있다.