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

프로그래머스의 가장 먼 노드 (Lv3) 문제이다.

[ 문제풀이 ]

1번 노드와 가장 멀리 떨어진 노드가 몇 개 인지 구해야 하는 문제이다.

본인은 이 문제를 2가지 파트로 나누어서 접근하였다.

1. 1번 노드와 각 노드들 간의 거리 구하기 + 그 중 가장 거리가 먼 노드의 길이 구하기

2. 1번을 통해서 구한 가장 길이가 먼 노드와 1번 노드와의 거리가 같은 노드들의 갯수 구하기

핵심은 1번 과정이다. 1번과 각 노드들 간의 거리를 구하는 부분인데, 본인은 이 부분을 2가지 방법으로 구해보았다.

하나는 완전탐색, 완전탐색 중에서도 너비우선탐색(BFS)를 이용해서 1번과 각 노드들 간의 거리를 구해 주었다.

또 한가지 방법은 다익스트라 알고리즘을 이용한 거리를 구하는 방식이다. 사실, 모든 거리가 '1'로 동일하기 때문에 다익스트라 알고리즘을 사용하지는 않아도 되지만 다익스트라 알고리즘으로도 한번 풀이해 보았다.

위에서 언급한 어떤 방법을 통해서 구하든지 중요한 것은, 각 노드들 간의 거리를 구하는 과정에서, 가장 거리가 먼 거리를 저장해 놓는 것과, 각 노드들과 1번 노드의 거리를 저장해 주어야 한다.

1번 노드와 각 노드들 간의 거리를 저장해 놓고, 가장 거리가 먼 거리를 저장해 놓으면, 이 거리와 각 노드들 간의 거리를 비교해서 가장 먼 노드들이 몇 개가 있는지 판단할 수 있기 때문이다.

[ BFS를 이용한 소스코드 ]

#include <string>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
 
vector<int> V[20010];
int Visit[20010];
 
int BFS(int n)
{
    memset(Visit, -1, sizeof(Visit));
    int Max = 0;
    queue<pair<int, int>> Q;
    Q.push(make_pair(1, 0));
    Visit[1] = 0;
 
    while (Q.empty() == 0)
    {
        int Cur = Q.front().first;
        int Dist = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < V[Cur].size(); i++)
        {
            int Next = V[Cur][i];
            if (Visit[Next] == -1)
            {
                Visit[Next] = Dist + 1;
                Q.push(make_pair(Next, Dist + 1));
                if (Max < Dist + 1) Max = Dist + 1;
            }
        }
    }
    return Max;
}
 
int solution(int n, vector<vector<int>> edge) 
{
    int answer = 0;
    for (int i = 0; i < edge.size(); i++)
    {
        int A = edge[i][0];
        int B = edge[i][1];
        V[A].push_back(B);
        V[B].push_back(A);
    }
    
    int Dist = BFS(n);
    for (int i = 2; i <= n; i++)
    {
        if (Visit[i] == Dist) answer++;
    }
    return answer;
}

[ Dijkstra를 이용한 소스코드 ]

#include <string>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
 
vector<int> V[20010];
int Dist[20010];
int Max;
 
void Dijkstra()
{
    priority_queue<pair<int, int>> PQ;
    PQ.push(make_pair(0, 1));
    Dist[1] = true;
 
    while (PQ.empty() == 0)
    {
        int Cur_Dist = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        for (int i = 0; i < V[Cur].size(); i++)
        {
            int Next = V[Cur][i];
 
            if (Dist[Next] > Cur_Dist + 1)
            {
                Dist[Next] = Cur_Dist + 1;
                PQ.push(make_pair(-Dist[Next], Next));
                if (Max < Dist[Next]) Max = Dist[Next];
            }
        }
    }
}
 
int solution(int n, vector<vector<int>> edge) 
{
    int answer = 0;
    for (int i = 0; i < edge.size(); i++)
    {
        int A = edge[i][0];
        int B = edge[i][1];
        V[A].push_back(B);
        V[B].push_back(A);
    }
    for (int i = 1; i <= n; i++) Dist[i] = 2e9;
    Dijkstra();
    for (int i = 2; i <= n; i++)
    {
        if (Dist[i] == Max) answer++;
    }
    return answer;
}