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

• 출처: 프로그래머스 49189
• 분류: 그래프 · Lv.3

문제

노드 수 n과 간선 목록 edge가 주어진다. 1번 노드에서 최단 경로로 가장 멀리 떨어진 노드의 개수를 반환한다. 간선은 양방향이다.

핵심

가중치 없는 그래프에서 1번 노드 기준 최단 거리 → BFS. 최대 거리와 같은 노드 수를 세면 된다.

풀이

#include <vector>
#include <queue>
using namespace std;

struct Node { int id, dist; };

int solution(int n, vector<vector<int>> edge) {
    vector<vector<int>> adj(n + 1);
    for (auto& e : edge) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }

    vector<int> dist(n + 1, -1);
    queue<Node> q;
    q.push({1, 0});
    dist[1] = 0;

    int maxDist = 0;

    while (!q.empty()) {
        auto [id, d] = q.front();
        q.pop();

        for (int next : adj[id]) {
            if (dist[next] != -1) continue;

            dist[next] = d + 1;
            if (dist[next] > maxDist) maxDist = dist[next];
            q.push({next, d + 1});
        }
    }

    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == maxDist) count++;
    }
    return count;
}

메모

• 인접 리스트 vs 인접 행렬
  • 노드 수 최대 20,000이므로 인접 행렬(20,000²)은 메모리 초과다. 인접 리스트를 쓴다
  • 간선 수 최대 50,000이므로 인접 리스트의 공간은 O(V + E)로 충분하다
• dist 배열의 역할
  • dist[i] = -1이면 미방문이다. 별도 visited 배열 없이 방문 여부와 거리를 동시에 관리한다
  • dist 배열에 push 시점에 거리를 기록하므로 visited를 push할 때 찍는 것과 동일한 효과다
• 격자 BFS와의 차이
  • 게임 맵 최단거리는 격자(2D 배열)에서 4방향 탐색이다. 이 문제는 인접 리스트 기반 일반 그래프다
  • 격자는 dx/dy 배열로 이웃을 순회하고, 일반 그래프는 adj[id]로 이웃을 순회한다. BFS 구조 자체는 동일하다

복잡도

풀이	시간	공간
BFS	O(V + E)	O(V + E)