algospot TSP1 여행하는 외판원 문제 1

문제

https://www.algospot.com/judge/problem/read/TSP1

걸린 시간

-

풀이

C++

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm> // sort
#include <string.h> // memset
using namespace std;

#define MAX 8
#define INF 987654321

int N;
double city[MAX][MAX];

double shortestPath(vector<int>& path, vector<int>& visited, double currentLength){
    // 기저 사례
    if(path.size() == N)
        return currentLength;
    // 매우 큰 값으로 초기화
    double ret = INF;
    for(int next = 0; next < N; next++){
        if(visited[next]) continue;
        visited[next] = 1;
        int here = path.back();
        path.push_back(next);
        // 재귀 호출
        double cand = shortestPath(path, visited, currentLength + city[here][next]);
        ret = min(ret, cand);
        visited[next] = 0;
        path.pop_back();
    }
    return ret;
}

int main(){
    int tc;
    scanf("%d", &tc);
    while(tc--){
        scanf("%d", &N);
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                scanf("%lf", &city[i][j]);
        double ans = INF;
        for(int i = 0; i < N; i++){
            vector<int> visited(MAX);
            vector<int> path;
            visited[i] = 1;
            path.push_back(i);
            double tmp = shortestPath(path, visited, 0);
            if(ans > tmp)
                ans = tmp;
        }
        printf("%.10lf\n", ans);
    }
    return 0;
}

위 알고리즘은 각 도시 n 에서 출발하여 모든 도시를 한번씩 방문하는 경로 (n-1)! 중 가장 짧은 값을 출력한다.

문제에서 주어질 수 있는 최대 도시의 수가 8개이므로 완전 탐색을 사용하여도 7! * 8 = 40320 으로 여유있게 계산할 수 있다.