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

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

프로그래머스

 

다익스트라를 구한 뒤, 가장 값이 큰 거리의 개수를 구하는 문제이다.  오랜만에 하니까 또 굉장히 헷갈렸다.

• A에 연결된 간선을 빠르게 파악하기 위해서 인자로 전달받은 edge를  graph로 변경한다. graph[1] 은 1번 노드에 연결된 모든 간선이 vector 안에 담겨있다.
• 다익스트라 알고리즘은 1번부터 시작하여, 옆노드의 거리를 갱신한 뒤 다음 검사노드를 찾기 위해서 priority queue가 필요하다. 현재 검사하지 않은 노드 중 가장 거리가 적은 노드먼저 검사하는것이 다익스트라의 기본이다. 이를 위해 pair<int,int> 를 이용한다. first값은 거리로, pq에서 거리순으로 정렬될수 있게끔 한다. second값은 노드의 번호이다.

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

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    vector<vector<int>> graph(n + 1);
    
    // 그래프 생성 (무향 그래프)
    for (auto &e : edge) {
        graph[e[0]].push_back(e[1]);
        graph[e[1]].push_back(e[0]);
    }

    // 다익스트라 알고리즘을 위한 최소 힙 (우선순위 큐)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    vector<int> dist(n + 1, INT_MAX);  // 최소 거리 배열
    
    // 시작점 (1번 노드)
    dist[1] = 0;
    pq.push({0, 1}); // (거리, 노드)

    while (!pq.empty()) {
        int current_dist = pq.top().first;
        int current_node = pq.top().second;
        pq.pop();

        // 현재 저장된 거리보다 크다면 무시
        if (current_dist > dist[current_node]) continue;

        // 인접한 노드들 검사
        for (int next : graph[current_node]) {
            int new_dist = current_dist + 1; // 가중치 1

            if (new_dist < dist[next]) {
                dist[next] = new_dist;
                pq.push({new_dist, next});
            }
        }
    }

    // 가장 먼 거리 찾기
    int maxDist = 0;
    int answer = 0;
    
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INT_MAX) continue; // 연결되지 않은 노드는 제외

        if (dist[i] > maxDist) {
            maxDist = dist[i];
            answer = 1;
        } else if (dist[i] == maxDist) {
            answer++;
        }
    }

    return answer;
}