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

 

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

프로그래머스

 이 문제는 전형적인 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘으로 문제를 풀기 위해서, 주어진 edges에서 주어진 vertex 배열에서 노드 a와 노드 b 사이의 거리를 1로 둔 다음 알고리즘을 이용하면 된다. 이 문제를 풀기 위해 구상한 절차는 다음곽 같다.

1. 주어진 vertex 배열의 정보를 다익스트라 알고리즘에 이용할 수 있게 변형시켜 저장한다.
2. 시작 노드(1번 노드)부터 다른 노드까지의 최소 거리를 저장할 변수(배열)의 값을 최대한 크게 초기화한다.
3. 다익스트라 알고리즘을 이용해 시작 노드부터 각 노드까지의 최소 거리를 계산한다.
4. 거리의 최대값과 이 때의 노드의 개수를 저장할 변수를 이용하여, 모든 거리를 비교한다.
   1. 현재 검사하는 노드까지의 거리가, 저장된 최대값보다 크다면 최대값을 저장한 후, 노드의 개수는 1로 설정한다.
   2. 현재 검사하는 노드까지의 거리가, 저장된 쵀대값과 같다면, 노드의 개수를 1 증가시킨다.

#include <string>
#include <vector>
#include <queue>
#include <map>

using namespace std;

#define MAX 20011
#define START 1

int dist[MAX];
vector<int> links[MAX];

int Check(int nodeNum)
{
    int maxDist = -1;
    int maxDistNum = 0;

    priority_queue<pair<int, int>> pq;
    pq.push({ START, 0 });

    dist[START] = 0;

    while(!pq.empty())
    {
        int curNode = pq.top().first;
        int curDist = -pq.top().second;
        pq.pop();

        if (dist[curNode] < curDist)
            continue;

        for (int i = 0; i < links[curNode].size(); ++i)
        {
            int nxtNode = links[curNode][i];
            int nxtDist = curDist + 1;

            if (dist[nxtNode] > nxtDist)
            {
                dist[nxtNode] = nxtDist;
                pq.push({ nxtNode, -nxtDist });
            }
        }
    }

    for (int node = 2; node <= nodeNum; ++node)
    {
        if (maxDist < dist[node])
        {
            maxDist = dist[node];
            maxDistNum = 1;
        }
        else if (maxDist == dist[node])
            ++maxDistNum;
    }

    return maxDistNum;
}

int solution(int n, vector<vector<int>> vertex) 
{
    for (int i = 0; i < MAX; ++i)
        dist[i] = MAX + MAX + MAX;

    for (int i = 0; i < vertex.size(); ++i)
    {
        int nodeA = vertex[i][0];
        int nodeB = vertex[i][1];

        links[nodeA].push_back(nodeB);
        links[nodeB].push_back(nodeA);
    }

    int answer = Check(n);

    return answer;
}