algospot TSP2

문제 링크입니다: https://algospot.com/judge/problem/read/TSP2

비트마스크라는 개념을 오랜만에 접했습니다.

C언어 입문했을 때 개념책에서 잠깐 비트라는 개념을 접하고, 학교에서 어셈블리언어 실습 시간에 잠깐 접한 비트마스크를 이런식으로 사용할 수 있다는 것을 처음 알았습니다.

역시 알고리즘은 끝이 없는 학문인 것 같습니다. 나름대로 이해한 부분을 주석으로 작성해봤습니다.

/*

여행하는 외판원 문제를 해결하는 동적 계획법 알고리즘

visited를 bool형 배열로 작성하는 대신 비트마스크를 활용해 메모리를 아꼈다

*/

#include <iostream>

#include <algorithm>

#include <bitset>

using namespace std;

 

const int MAX = 15;

const double INF = 987654321.0;

 

int N;

double dist[MAX][MAX];

//사실상 double cache[MAX][2^MAX]

double cache[MAX][1<<MAX]; //-1로 초기화해둔다

//here:현재 위치

//visited: 각 도시의 방문 여부

//here에서 시작해 남은 도시들을 방문할 수 있는 최단 경로의 길이를 반환

//나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이 반환

//항상 0번 도시에서 시작한다고 가정

double shortestPath2(int here, int visited)

{

        //기저 사례: 모든 도시를 다 방문했을 때는 0번 도시로 돌아가고 종료

        if (visited == (1 << N) - 1) //비트마스크 활용, (2^N)-1이면 모든 자릿수가 1이므로 전체 다 방문했다는 뜻

               return 0;

        //메모이제이션

        double &result = cache[here][visited];

        if (result > 0)

               return result;

        result = INF; //매우 큰 값으로 초기화

        //다음 방문할 도시를 전부 시도해 본다

        for (int next = 0; next < N; next++)

        {

               //이미 방문한 도시인 경우

               if (visited & (1 << next)) //비트마스크 활용 next만큼 왼쪽으로 쉬프트, 즉 2^next=1면 visited&(1<<next)는 1이므로 참

                       continue;

               double candidate = dist[here][next] + shortestPath2(next, visited + (1 << next)); //방문했다는 것을 비트마스크 활용

               result = min(result, candidate);

        }

        return result;

}

 

void initialize(void)

{

        for (int i = 0; i < MAX; i++)

               for (int j = 0; j < (1<<MAX); j++)

                       cache[i][j] = -1.0; //double에 대해서는 memset 적용 안됨

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 0 || test_case>50)

               exit(-1);

 

        cout.setf(ios::fixed);

        for (int i = 0; i < test_case; i++)

        {

               cin >> N;

               if (N<3 || N>MAX)

                       exit(-1);

              

               cin.precision(10);

               for (int j = 0; j < N; j++)

                       for (int k = 0; k < N; k++)

                              cin >> dist[j][k];

 

               initialize();

               double result = INF;

               for (int i = 0; i < N; i++)

                       result = min(result, shortestPath2(i, 1 << i)); //각 도시를 방문했다는 것을 1<<i로

               cout.precision(10);

               cout << result << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략