C++ 프로그램으로 1번 정점에서 시작하는 사전순 최소 BFS 출력하기

문제 개요

N개의 정점과 M개의 간선으로 이루어진 연결 그래프가 주어졌을 때, 1번 정점에서 시작하는 사전순으로 가장 작은 BFS 순회 결과를 출력하는 것이 이 글의 목표입니다.

여기서 '사전순(lexicographically smallest)'이란, 시작 정점부터 탐색이 끝나는 지점까지 매 단계에서 항상 번호가 가장 작은 정점을 먼저 방문한다는 의미입니다. 모든 정점은 1부터 N까지 번호가 매겨집니다.

예제 입력과 출력

입력: N = 5, M = 5
    간선 (1, 4)
    간선 (3, 4)
    간선 (5, 4)
    간선 (3, 2)
    간선 (1, 5)

출력: 1 4 3 2 5

접근 방법: 일반 큐 대신 우선순위 큐 사용

일반적인 BFS 탐색에서는 FIFO(선입선출) 방식의 단순 큐를 사용하지만, 이 문제에서는 우선순위 큐(최소 힙, min heap)를 활용하는 것이 핵심입니다.

동작 방식은 다음과 같습니다.
- 어떤 노드를 방문할 때마다 그 노드의 인접 노드들을 우선순위 큐에 삽입합니다.
- 새로운 노드를 방문할 때는 항상 우선순위 큐에 남아 있는 노드 중 인덱스가 가장 작은 노드가 선택됩니다.
- 1번 정점부터 탐색을 시작해, 노드를 방문할 때마다 즉시 출력합니다.

알고리즘

시작
단계 1 -> 함수 void lexo(vector<int> array[], int n) 선언
    bool arr[n + 1] 선언
    memset(arr, 0, sizeof arr) 호출
    STL priority_queue<int, vector<int>, greater<int>> que 사용
    arr[1] = true 설정
    que.push(1) 호출
    While (!que.empty()) 반복
        int now = que.top()
        que.pop()
        now 출력
        For (auto p : array[now])
            IF (!arr[p])
                que.push(p)
                arr[p] = true
            End
        End
    End
단계 2 -> 함수 void edge(int i, int j, vector<int> ar[]) 선언
    ar[i].push_back(j) 호출
    ar[j].push_back(i) 호출
단계 3 -> main() 함수
    int n = 5, m = 5 선언
    vector<int> arr[n + 1] 사용
    edge(1, 4, arr) 호출
    edge(3, 4, arr) 호출
    lexo(arr, n) 호출
종료

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;

// 사전순 최소 BFS 탐색 함수
void lexo(vector<int> array[], int n){
    bool arr[n + 1];
    memset(arr, 0, sizeof arr);
    priority_queue<int, vector<int>, greater<int>> que; // 최소 힙
    arr[1] = true;
    que.push(1);
    while (!que.empty()){
        int now = que.top();
        que.pop();
        cout << now << " ";
        for (auto p : array[now]){
            if (!arr[p]){
                que.push(p);
                arr[p] = true;
            }
        }
    }
}

// 간선 추가 함수 (무방향 그래프)
void edge(int i, int j, vector<int> ar[]){
    ar[i].push_back(j);
    ar[j].push_back(i);
}

int main(){
    int n = 5, m = 5;
    vector<int> arr[n + 1]; // 인접 리스트
    edge(1, 4, arr);
    edge(3, 4, arr);
    edge(5, 4, arr);
    edge(3, 2, arr);
    edge(1, 5, arr);
    lexo(arr, n);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

1 4 3 2 5

출력 과정 상세 분석

예제 그래프에서 탐색이 진행되는 과정을 단계별로 살펴보면 다음과 같습니다.
1. 1번 정점을 방문하고, 인접 정점인 4와 5를 우선순위 큐에 삽입합니다.
2. 큐에서 가장 작은 값인 4를 꺼내 방문합니다. 4의 인접 정점 중 아직 방문하지 않은 3을 큐에 삽입합니다(1은 이미 방문했고, 5는 이미 큐에 존재).
3. 큐에서 3을 꺼내 방문하고, 인접 정점 2를 삽입합니다.
4. 2를 방문합니다. 2의 인접 정점 3은 이미 방문된 상태입니다.
5. 마지막으로 5를 방문하면 탐색이 종료됩니다.

따라서 최종 출력은 1 4 3 2 5가 됩니다.

주의할 점은, 노드를 큐에 삽입하는 시점에 방문 처리를 해야 한다는 것입니다. 큐에서 꺼낼 때 방문 여부를 검사하면 같은 노드가 여러 번 큐에 들어가 비효율적으로 동작할 수 있습니다.

시간 복잡도

모든 정점과 간선에 대해 우선순위 큐 연산(삽입·삭제)이 한 번씩 수행되며, 각 연산에는 O(log N)의 시간이 걸립니다. 따라서 전체 시간 복잡도는 O((N + M) log N)입니다. 공간 복잡도는 인접 리스트, 방문 배열, 우선순위 큐를 포함해 O(N + M)입니다.