Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ BFS 알고리즘으로 시작 정점에서 목적지까지의 모든 경로 출력하기

문제 개요

이 문제에서는 방향 그래프(directed graph)가 주어지며, 너비 우선 탐색(BFS)을 이용해 시작 정점(소스)에서 목적지 정점까지 이르는 모든 경로를 찾아 출력해야 합니다.

방향 그래프란 간선에 방향성이 있어 정점 a에서 정점 b로 한 방향으로만 이동할 수 있는 그래프를 의미합니다.

예시로 이해하기

다음 예시를 통해 문제를 살펴보겠습니다.

C++ BFS 알고리즘으로 시작 정점에서 목적지까지의 모든 경로 출력하기

Source = K, Destination = P일 때,

출력 결과

K -> T -> Y -> A -> P
K -> T -> Y -> P
K -> A -> P

위 결과는 K에서 출발하여 P에 도달하는 세 가지 경로를 모두 탐색하고 출력한 것입니다. 즉, 그래프를 순회하면서 K로부터 P까지 이어지는 유효한 경로를 모두 찾아낸 것입니다.

접근 방법

시작 정점에서 목적지까지의 모든 경로를 출력하려면 그래프를 순회하면서 지나온 경로를 저장하고, 그중 유효한 경로만 골라 출력해야 합니다.

DFS(깊이 우선 탐색)를 사용하면 이 과정이 비교적 간단하지만, BFS로 구현하는 것은 다소 까다롭습니다. 그 이유는 BFS는 정점 단위로 탐색하기 때문에, 각 정점뿐만 아니라 경로 자체를 함께 관리해야 하기 때문입니다.

이를 해결하기 위해 경로(vector)를 원소로 저장하는 큐(queue)를 활용합니다. 시작 노드부터 BFS 방식으로 그래프를 순회하면서, 큐에서 꺼낸 경로의 마지막 정점이 목적지에 도달했다면 해당 경로를 출력하고, 도달하지 않았다면 인접 정점을 추가한 새로운 경로를 만들어 다시 큐에 삽입합니다.

알고리즘 동작 과정

  1. 시작 정점만 포함된 초기 경로를 큐에 삽입합니다.
  2. 큐가 빌 때까지 다음 과정을 반복합니다.
  3. 큐에서 경로 하나를 꺼내고, 해당 경로의 마지막 정점을 확인합니다.
  4. 마지막 정점이 목적지라면 경로를 출력합니다.
  5. 마지막 정점과 인접한 정점 중 아직 경로에 포함되지 않은 정점을 추가한 새 경로를 만들어 큐에 삽입합니다.

C++ 구현 코드

아래 프로그램을 통해 해결 방법을 더 명확히 이해할 수 있습니다.

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

// 경로를 출력하는 함수
void printPath(vector<char>& path) {
    int size = path.size();
    for (int i = 0; i < size; i++)
    cout << path[i] << " ";
    cout << endl;
}

// 특정 정점이 이미 경로에 포함되어 있는지 확인하는 함수
int isVertexVisited(char x, vector<char>& path) {
    int size = path.size();
    for (int i = 0; i < size; i++)
    if (path[i] == x)
    return 1;
    return 0;
}

// BFS로 시작 정점에서 목적지까지의 모든 경로를 찾는 함수
void pathSourceToDestination(vector<vector<char> >&g, char src, char dst, int v) {
    queue<vector<char> > q;
    vector<char> path;
    path.push_back(src);
    q.push(path);
    while (!q.empty()) {
        path = q.front();
        q.pop();
        char last = path[path.size() - 1];
        // 마지막 정점이 목적지면 경로 출력
        if (last == dst)
        printPath(path);
        // 인접 정점 중 방문하지 않은 정점을 경로에 추가
        for (int i = 0; i < g[last].size(); i++) {
            if (!isVertexVisited(g[last][i], path)) {
                vector<char> newpath(path);
                newpath.push_back(g[last][i]);
                q.push(newpath);
            }
        }
    }
}

int main() {
    vector<vector<char> > g;
    int v = 4;
    g.resize(4);
    g['X'].push_back('S');
    g['X'].push_back('A');
    g['X'].push_back('N');
    g['A'].push_back('S');
    g['N'].push_back('X');
    g['N'].push_back('A');
    char src = 'N', dst = 'S';
    cout << "path from src " << src << " to dst " << dst << " are \n";
    pathSourceToDestination(g, src, dst, v);
    return 0;
}

실행 결과

path from src N to dst S are
N X S
N A S
N X A S

실행 결과를 보면 N에서 S까지 이르는 세 가지 경로(N → X → S, N → A → S, N → X → A → S)가 모두 출력됩니다. 이처럼 큐에 경로 자체를 저장하고 확장해 나가는 방식을 사용하면, BFS로도 시작 정점에서 목적지까지의 모든 경로를 효과적으로 찾아낼 수 있습니다.