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

가장 먼 노드

문제 링크

가장 먼 노드

분석

무방향 그래프에서 시작 노드인 1번 노드로부터 가장 멀리 떨어진 노드들의 개수를 구해야합니다.

BFS를 통해 최단거리를 구하고, 가장 멀리 떨어진 노드들의 개수를 세면 됩니다.

풀이

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    // 인접 리스트를 이용해 그래프 생성
    vector<vector<int>> graph(n + 1);
    for (const auto& e : edge)
    {
        graph[e[0]].push_back(e[1]);
        graph[e[1]].push_back(e[0]);
    }
    
    // 각 노드까지의 거리를 저장하는 벡터
    vector<int> distance(n + 1, 0);

    // 각 노드의 방문 여부를 저장하는 벡터
    vector<bool> visited(n + 1, false);
    
    // BFS를 위한 큐
    queue<int> q;
    q.push(1);
    visited[1] = true;
    
    while(!q.empty())
    {
        // 현재 노드
        int current = q.front();
        q.pop();
        
        // 현재 노드를 기준으로 방문 할 수 있는 인접 노드들을 탐색
        for (int next : graph[current])
        {
            // 방문하지 않은 인접 노드인 경우
            if (!visited[next])
            {
                // 방문 처리해주며, 거리를 저장한다.
                visited[next] = true;
                distance[next] = distance[current] + 1;
                q.push(next);
            }
        }
    }
    
    // 최단 거리 중 가장 먼 거리를 구한다.
    int maxDistance = *max_element(distance.begin(), distance.end());
    
    // 가장 먼 거리를 가지는 노드들의 개수를 계산한다.
    for (int e : distance)
    {
        if (e == maxDistance)
        {
            ++answer;
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n + e)$입니다.

• 그래프를 생성하는 반복문 $O(e)$
  • e는 간선의 수입니다.
• BFS 탐색 $O(n + e)$
  • n은 노드의 수입니다.
• 최단 거리 중 가장 먼 거리를 계산하는 max_element $O(n + 1) \approx O(n)$
• 가장 먼 노드 개수 세기 $O(n + 1) \approx O(n)$
• $O(e) + O(n + e) + O(n) + O(n)$

공간 복잡도는 $O(n + e)$입니다.

• 그래프를 나타내는 벡터 $O(n + 1)$, 최악의 경우 $O(n + e)$
• 각 노드까지의 거리를 저장하는 벡터 vector<int> distance $O(n + 1) \approx O(n)$
• 각 노드의 방문 여부를 저장하는 벡터 vector<bool> visited $O(n + 1) \approx O(n)$
• BFS 큐 $O(n)$
• $O(n + e) + O(n) + O(n) + O(n)$

테스트 성능

테스트 1 〉 통과 (0.02ms, 4.16MB)
테스트 2 〉 통과 (0.01ms, 4.06MB)
테스트 3 〉 통과 (0.02ms, 4.16MB)
테스트 4 〉 통과 (0.12ms, 4.14MB)
테스트 5 〉 통과 (0.29ms, 4.13MB)
테스트 6 〉 통과 (0.72ms, 4.32MB)
테스트 7 〉 통과 (5.84ms, 10.6MB)
테스트 8 〉 통과 (12.02ms, 14MB)
테스트 9 〉 통과 (8.42ms, 13.9MB)