[알고리즘 문제] BFS - 프로그래머스 가장 먼 노드(level 3)

문제 이해

노드 n개와 양방향 간선 목록이 주어집니다. 1번 노드에서 각 노드까지 최단 경로로 이동했을 때, 지나가는 간선 수가 가장 큰 노드가 몇 개인지 구하는 문제입니다.

가장 먼 노드
= 1번 노드로부터의 최단 거리가 가장 큰 노드

단순히 깊게 이동한 경로를 찾는 것이 아니라 모든 노드의 최단 거리를 비교해야 합니다. 같은 노드로 가는 경로가 여러 개라면 그중 간선 수가 가장 적은 경로만 거리로 사용합니다.

BFS를 선택한 이유

모든 간선의 이동 비용이 1인 가중치 없는 그래프에서는 BFS로 최단 거리를 구할 수 있습니다. BFS는 시작점에서 거리가 0인 노드, 거리 1인 노드, 거리 2인 노드 순서로 탐색 범위를 넓힙니다.

거리 0: 시작 노드
거리 1: 시작 노드와 직접 연결된 노드
거리 2: 거리 1 노드에서 처음 발견한 노드
거리 3: 거리 2 노드에서 처음 발견한 노드
...

따라서 어떤 노드를 처음 발견한 순간의 경로보다 더 짧은 경로가 나중에 등장할 수 없습니다. 이 성질 덕분에 별도의 거리 갱신을 반복하지 않고 최초 방문 거리만 저장하면 됩니다.

DFS도 모든 노드를 방문할 수 있지만 처음 도착한 경로가 최단 경로라는 보장은 없습니다. 가중치가 없는 그래프의 최소 간선 수를 구할 때는 레벨 순서로 탐색하는 BFS가 알맞습니다.

인접 리스트 만들기

입력은 간선 목록이므로 현재 노드에서 이동할 수 있는 이웃을 빠르게 찾을 수 있도록 인접 리스트로 변환합니다. 간선은 양방향이기 때문에 a → b와 b → a를 모두 저장해야 합니다.

vector<vector<int>> graph(n + 1);

for (const auto& edge : vertex) {
    int a = edge[0];
    int b = edge[1];

    graph[a].push_back(b);
    graph[b].push_back(a);
}

노드 번호가 1부터 시작하므로 배열 크기는 n + 1로 잡습니다. 인접 행렬을 사용하면 n이 최대 20,000일 때 불필요한 공간을 크게 사용하므로 간선 수에 비례하는 인접 리스트가 적합합니다.

거리와 방문 여부 기록하기

거리 배열을 -1로 초기화하면 하나의 배열이 두 역할을 맡을 수 있습니다.

distance[node] == -1  아직 방문하지 않은 노드
distance[node] >= 0   1번 노드부터 node까지의 최단 거리

시작 노드의 거리는 0으로 바꾸고 큐에 넣습니다. 큐에서 현재 노드를 꺼낸 뒤 아직 방문하지 않은 이웃만 탐색합니다. 이웃의 거리는 현재 노드의 거리보다 간선 하나만큼 멀기 때문에 distance[current] + 1입니다.

distance[1] = 0;
q.push(1);

while (!q.empty()) {
    int current = q.front();
    q.pop();

    for (int next : graph[current]) {
        if (distance[next] != -1) {
            continue;
        }

        distance[next] = distance[current] + 1;
        q.push(next);
    }
}

방문 표시는 큐에서 꺼낼 때가 아니라 큐에 넣을 때 해야 합니다. 그래야 여러 노드가 같은 이웃을 발견해 큐에 중복으로 넣는 일을 막을 수 있습니다.

예제로 탐색 흐름 확인하기

예제 그래프를 1번 노드부터 BFS로 탐색하면 거리가 다음 순서로 정해집니다.

거리 0: 1
거리 1: 2, 3
거리 2: 4, 5, 6

distance = [-, 0, 1, 1, 2, 2, 2]

4번 노드는 2번과 3번 양쪽에서 갈 수 있지만, 먼저 발견한 거리 2가 최단 거리입니다. 이후 다른 간선에서 4번을 다시 만나도 이미 방문했으므로 건너뜁니다. 가장 큰 최단 거리는 2이고 해당하는 노드는 4, 5, 6이므로 답은 3입니다.

가장 먼 노드 세기

BFS가 끝나면 거리 배열을 두 번 순회합니다. 먼저 최댓값을 구하고, 다시 그 값과 같은 노드의 수를 셉니다.

int maxDistance = 0;

for (int node = 1; node <= n; ++node) {
    maxDistance = max(maxDistance, distance[node]);
}

int answer = 0;

for (int node = 1; node <= n; ++node) {
    if (distance[node] == maxDistance) {
        ++answer;
    }
}

두 순회 모두 O(n)이고 전체 BFS 복잡도보다 커지지 않습니다. 최댓값을 먼저 확정한 뒤 개수를 세므로 집계 로직도 쉽게 읽을 수 있습니다.

최종 코드

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

using namespace std;

int solution(int n, vector<vector<int>> vertex)
{
    vector<vector<int>> graph(n + 1);

    for (const auto& edge : vertex) {
        int a = edge[0];
        int b = edge[1];

        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    vector<int> distance(n + 1, -1);
    queue<int> q;

    distance[1] = 0;
    q.push(1);

    while (!q.empty()) {
        int current = q.front();
        q.pop();

        for (int next : graph[current]) {
            if (distance[next] != -1) {
                continue;
            }

            distance[next] = distance[current] + 1;
            q.push(next);
        }
    }

    int maxDistance = 0;

    for (int node = 1; node <= n; ++node) {
        maxDistance = max(maxDistance, distance[node]);
    }

    int answer = 0;

    for (int node = 1; node <= n; ++node) {
        if (distance[node] == maxDistance) {
            ++answer;
        }
    }

    return answer;
}

초고의 구현에서 사용하지 않는 <string> 헤더를 제거하고, std::max를 사용하는 코드임을 명확히 하기 위해 <algorithm>을 포함했습니다. 나머지는 BFS의 기본 구조를 그대로 따릅니다.

복잡도와 체크포인트

• 시간복잡도는 O(n + e)
• 노드 수를 n, 간선 수를 e라 하면 BFS에서 각 노드와 양방향 간선을 상수 번 확인합니다. 거리 집계의 O(n)을 더해도 같습니다.
• 공간복잡도는 O(n + e)
• 인접 리스트가 모든 간선을 저장하고, 거리 배열과 큐가 최대 노드 수에 비례하는 공간을 사용합니다.
• 양방향 간선을 양쪽에 저장한다
• graph[a]에 b만 넣으면 입력 방향에 따라 일부 노드에 도달할 수 없습니다.
• 거리 배열로 방문 여부를 함께 관리한다
• -1을 미방문 상태로 정하면 별도의 visited 배열 없이 중복 탐색을 막을 수 있습니다.
• BFS의 적용 조건을 확인한다
• 간선마다 비용이 다르다면 일반 BFS가 최단 거리를 보장하지 않습니다. 이 문제는 모든 간선 비용이 동일하므로 사용할 수 있습니다.

정리

• 가장 먼 노드는 1번 노드로부터 최단 거리가 가장 큰 노드다.
• 가중치가 없는 그래프에서는 BFS의 최초 방문 거리가 최단 거리다.
• 양방향 간선을 인접 리스트의 양쪽에 저장한다.
• 거리 배열을 -1로 초기화해 방문 여부와 최단 거리를 함께 관리한다.
• BFS가 끝난 뒤 최대 거리와 그 거리를 가진 노드 수를 구한다.

이전에 학습한 BFS 예제와 거의 같은 구조여서 알고리즘을 빠르게 선택할 수 있었습니다. 이번 문제를 통해 “가중치 없는 그래프의 최단 거리”라는 조건을 발견하면 큐, 거리 배열, 최초 방문이라는 BFS의 기본 틀로 바로 연결할 수 있음을 확인했습니다.