C++로 푸는 순회 판매원 문제(TSP): 비가중 그래프의 최단 경로 구하기

순회 판매원 문제(Travelling Salesman Problem, TSP)는 모든 도시를 한 번씩 방문한 뒤 다시 출발 도시로 돌아오는 최단 경로를 계산하는 대표적인 알고리즘 문제입니다. 그래프 관점에서 보면, 그래프에 존재하는 모든 노드를 거쳐 다시 시작 노드로 복귀하는 가장 짧은 경로를 찾는 방식으로 활용할 수 있습니다.

이 글에서는 C++를 이용해 비가중(unweighted) 그래프의 최단 순회 경로를 구하는 프로그램을 소개합니다. 핵심 아이디어는 출발점을 제외한 나머지 정점들의 모든 순열(permutation)을 생성해 각 경우의 총 이동 거리를 계산하고, 그중 최솟값을 반환하는 완전 탐색(brute-force) 방식입니다.

알고리즘

시작
    정점 개수 vr = 4를 전역 변수로 정의한다.
    순회 판매원 문제를 수행하는 정수형 함수 TSP를 선언한다.
    2차원 행렬 형태의 그래프 grph[][]와 정수형 변수 p를 매개변수로 전달한다.
    벡터(vector) 자료형의 변수 ver을 선언한다.
    for (int i = 0; i < vr; i++)
        if (i != p) 이면
            push_back(i) 함수를 호출하여 출발 정점을 제외한 모든 정점을 ver에 저장한다.
            그래프의 최소 가중치를 저장하기 위해 m_p = INT_MAX로 초기화한다.
    do
        정수형 변수 cur_pth, k를 선언한다.
            cur_pth = 0 으로 초기화한다.
            k = p 로 초기화한다.
        for (int i = 0; i < ver.size(); i++)
            cur_pth += grph[k][ver[i]]
            k = ver[i]
        cur_pth += grph[k][p]   // 마지막 정점에서 출발점으로 복귀하는 비용 추가
        m_p = min(m_p, cur_pth) // 최소 가중치 값 갱신
        while (next_permutation(ver.begin(), ver.end())) // 다음 순열이 존재하는 동안 반복
    m_p를 반환한다.
    정수형 2차원 행렬 grph[][]로 그래프를 선언하고 값을 초기화한다.
    정수형 변수 p를 선언하고 p = 0으로 초기화한다.
    "The result is: "를 출력한다.
    TSP() 함수의 반환값을 출력한다.
끝.

예제 코드

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

int TSP(int grph[][vr], int p) { // 순회 판매원 문제 구현
    vector<int> ver;
    for (int i = 0; i < vr; i++)
        if (i != p)
            ver.push_back(i);
    int m_p = INT_MAX; // 그래프의 최소 가중치 저장
    do {
        int cur_pth = 0;
        int k = p;
        for (int i = 0; i < ver.size(); i++) {
            cur_pth += grph[k][ver[i]];
            k = ver[i];
        }
        cur_pth += grph[k][p];
        m_p = min(m_p, cur_pth); // 최소 가중치 값 갱신
    }
    while (next_permutation(ver.begin(), ver.end()));
    return m_p;
}

int main() {
    int grph[][vr] = { { 0, 5, 10, 15 },  // 행렬 형태의 그래프 값
                       { 5, 0, 20, 30 },
                       { 10, 20, 0, 35 },
                       { 15, 30, 35, 0 }
    };
    int p = 0;
    cout<< "\n The result is: "<< TSP(grph, p) << endl;
    return 0;
}

실행 결과

The result is: 75

코드 설명

위 예제에서 그래프는 4×4 인접 행렬로 표현되며, 각 원소는 두 정점 사이의 이동 비용(거리)을 나타냅니다. 출발 정점 p = 0을 제외한 정점 {1, 2, 3}의 모든 순열을 next_permutation으로 하나씩 생성하면서, 각 순서대로 방문했을 때의 총 이동 비용 cur_pth를 누적합니다. 마지막에는 마지막 방문 정점에서 출발점으로 돌아오는 비용까지 더한 뒤, 지금까지의 최솟값 m_p와 비교해 갱신합니다.

모든 순열에 대한 탐색이 끝나면 m_p에 남아 있는 값이 곧 최적 순회 경로의 총비용이며, 이 예제에서는 75가 출력됩니다. 참고로 이 완전 탐색 방식은 정점 수가 n일 때 시간 복잡도가 O(n!)이므로 정점이 많아지면 비효율적이며, 실무에서는 동적 계획법(DP) 기반의 헬드-카프(Held-Karp) 알고리즘이나 근사 기법이 주로 사용됩니다.