C++로 그래프에서 두 정점 사이의 모든 경로 개수 구하기

이 튜토리얼에서는 그래프에서 두 정점 사이의 경로 개수를 구하는 프로그램을 만들어 보겠습니다.

방향 그래프(directed graph)가 주어지며, 우리가 해야 할 일은 주어진 두 정점 사이에 존재할 수 있는 모든 경로의 개수를 세는 것입니다.

문제 접근 방법

이 문제는 깊이 우선 탐색(DFS)과 백트래킹(backtracking) 기법을 활용하면 효과적으로 해결할 수 있습니다. 시작 정점에서 출발해 인접한 정점들을 하나씩 방문하다가 도착 정점에 도달할 때마다 경로 개수를 1씩 증가시키고, 한 정점에 대한 탐색이 끝나면 방문 표시를 되돌려서 다른 경로에서도 해당 정점을 지나갈 수 있도록 하는 것이 핵심입니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
// 방향 그래프 생성
class Graph{
    int V;
    list<int> *adj;
    void countPathsUtil(int, int, bool [], int &);
public:
    // 생성자
    Graph(int V);
    void addEdge(int u, int v);
    int countPaths(int s, int d);
};
Graph::Graph(int V){
    this->V = V;
    adj = new list<int>[V];
}
void Graph::addEdge(int u, int v){
    adj[u].push_back(v);
}
int Graph::countPaths(int s, int d){
    // 모든 정점을 방문하지 않음으로 표시
    bool *visited = new bool[V];
    memset(visited, false, sizeof(visited));
    int pathCount = 0;
    countPathsUtil(s, d, visited, pathCount);
    return pathCount;
}
void Graph::countPathsUtil(int u, int d, bool visited[], int &pathCount){
    visited[u] = true;
    // 현재 정점이 도착 정점과 같다면 경로 개수 증가
    if (u == d)
        pathCount++;
    // 현재 정점이 도착 정점이 아니라면
    else {
        list<int>::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
            if (!visited[*i])
                countPathsUtil(*i, d, visited, pathCount);
    }
    visited[u] = false;
}
int main(){
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(0, 3);
    g.addEdge(2, 0);
    g.addEdge(2, 1);
    g.addEdge(1, 3);
    int s = 2, d = 3;
    cout << g.countPaths(s, d);
    return 0;
}

코드 동작 원리

• Graph 클래스: 정점의 개수(V)와 인접 리스트(adj)를 멤버로 가지며, addEdge() 함수를 통해 간선을 추가합니다.
• countPaths(): 방문 여부를 저장할 배열을 초기화한 뒤, countPathsUtil()을 호출하고 최종 경로 개수를 반환합니다.
• countPathsUtil(): 현재 정점을 방문 처리한 후, 현재 정점이 도착 정점이라면 경로 개수를 증가시킵니다. 그렇지 않다면 아직 방문하지 않은 인접 정점들을 재귀적으로 탐색합니다. 탐색이 끝나면 현재 정점의 방문 표시를 해제하여(백트래킹) 다른 경로에서도 이 정점을 거칠 수 있게 합니다.

출력 결과

3

위 예제에서 정점 2에서 정점 3으로 가는 경로는 2→0→3, 2→0→1→3, 2→1→3으로 총 3개이므로, 프로그램은 올바르게 3을 출력합니다.