ID : TSP1(여행하는 외판원1) 난이도 : 하 (재귀 완전탐색)

문제 : https://algospot.com/judge/problem/read/TSP1

#include <iostream>
#include <vector>
 
class CustomMap
{
public:
    const double INF = 987654321;
 
    double mfShortestPath;
    int mnNumOfCity;
    double mfCurrentLength;
    std::vector<std::vector<double>> mListOfDist;
    std::vector<int> mPath;
    std::vector<bool> mVisited;
 
    void FindShortPath();
 
private:
 
    void _InitVar();
    double _ShortestPath(std::vector<int>& parPath, std::vector<bool>& parVisited, double parCurrentLength);
 
};
 
 
 
int main()
{
    int nTestCase;
    std::vector<CustomMap> customMapList;
 
    std::cin >> nTestCase;
    getchar();
 
 
    for (int i = 0; i < nTestCase; ++i)
    {
        CustomMap tmpCustomMap;
        std::vector<double> tmpDistList;
 
 
        std::cin >> tmpCustomMap.mnNumOfCity;
        getchar();
 
        for (int j = 0; j < tmpCustomMap.mnNumOfCity; ++j)
        {
            tmpDistList.clear();
            for (int k = 0; k < tmpCustomMap.mnNumOfCity; ++k)
            {
                double fDist;
                std::cin >> fDist;
                tmpDistList.push_back(fDist);
 
            }
            tmpCustomMap.mListOfDist.push_back(tmpDistList);
            getchar();
        }
        
        customMapList.push_back(tmpCustomMap);
        
    }
 
    for (auto tmpCustom : customMapList)
    {
        tmpCustom.FindShortPath();
        std::cout.precision(10);
        std::cout << std::fixed << tmpCustom.mfShortestPath << std::endl;
    }
 
 
 
    return 0;
}
 
void CustomMap::FindShortPath()
{
    _InitVar();
    
    mfShortestPath = INF;
    double fRet;
    
 
    //시작지점 고르기
    for (int i = 0; i < mnNumOfCity; ++i)
    {
        mVisited[i] = true;
        mPath.push_back(i);
 
        fRet = _ShortestPath(mPath, mVisited, 0);
 
        if (mfShortestPath > fRet)
        {
            mfShortestPath = fRet;
        }
 
        mVisited[i] = false;
        mPath.pop_back();
    }
    
}
 
void CustomMap::_InitVar()
{
    mPath.clear();
    mVisited.clear();
    for (int i = 0; i < mnNumOfCity; ++i)
    {
        mVisited.push_back(false);
    }
}
 
double CustomMap::_ShortestPath(std::vector<int>& parPath, std::vector<bool>& parVisited, double parCurrentLength)
{
    //parPath  지금까지 만든 경로
    //parVisited 각 도시의 방문 여부
    //parCurrentLength 지금까지 만든 경로의 길이
    //나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.
 
 
    //기저 사례 : 모든 도시를 다 방문했을 때는 시작 도시로 돌아가고 종료한다.
    if (parPath.size() == mnNumOfCity)
    {
        //return parCurrentLength + mListOfDist[0][parPath.back()];    //마지막 방문지점에서 처음지점으로돌아갈때
        return parCurrentLength;    //모든 경로를 방문했을때
    }
    double fRet = INF;    //매우 큰 값으로 초기화
    //다음 방문할 도시를 전부 시도해 본다.
 
    for (int next = 0; next < mnNumOfCity; ++next)
    {
        if (parVisited[next] == true)
        {
            continue;
        }
        int nHere = parPath.back();
        parPath.push_back(next);
        parVisited[next] = true;
        //나머지 경로를 재귀 호출을 통해 완성하고 가장 짧은 경로의 길이를 얻는다.
        double fCand = _ShortestPath(parPath, parVisited, parCurrentLength + mListOfDist[nHere][next]);
        if( fRet > fCand )
        {
            fRet = fCand;
        }
        parVisited[next] = false;
        parPath.pop_back();
    }
 
 
    return fRet;
}