Level 3. 가장 먼 노드

Level 3. 가장 먼 노드

 

 

그래프 탐색에서 단순 비용 갱신이 아니라, 이 문제처럼 최댓값 개수를 구하는 등 추가 작업이 필요할 때는 DFS보다는 BFS로 진행하는 것이 좋다.

 

이 문제는 전형적인 다익스트라 알고리즘 문제다.

• 모든 거리의 초깃값을 MAX로 설정하고, 시작점만 0으로 설정하는 것이 특징이다.
• 거리가 작으면 갱신하고 그 지점을 탐색하도록 한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

#define UNREACHABLE INT_MAX

using namespace std;

int solution(int n, vector<vector<int>> edge)
{
    int answer = 0, max;
    queue<int> que;
    vector<vector<int>> graph(n + 1);
    vector<int> distance(n + 1, UNREACHABLE);

    for (vector<int>& e : edge)
    {
        graph[e[0]].emplace_back(e[1]);
        graph[e[1]].emplace_back(e[0]);
    }

    max = distance[1] = 0;
    que.emplace(1);

    while (!que.empty())
    {
        int v = que.front(); que.pop();

        if (max < distance[v])
        {
            max = distance[v];
            answer = 1;
        }
        else
        {
            ++answer;
        }

        for (int adj : graph[v])
        {
            int dist = distance[v] + 1;

            if (dist < distance[adj])
            {
                distance[adj] = dist;
                que.emplace(adj);
            }
        }
    }

    return answer;
}