백준 2098번 외판원 순회

문제 링크입니다: https://www.acmicpc.net/problem/2098

http://jaimemin.tistory.com/365와 비슷한 문제였습니다.

다른점은 다시 해당 도시로 돌아오는 경로도 더해줘야하고 (i,j)와 (j,i)가 대칭이 아니라는 점이였습니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 16;

const int INF = 987654321;

 

int N;

int W[MAX][MAX];

int cache[MAX][1 << MAX];

 

int TSP(int here, int visited)

{

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

        if (visited == (1 << N) - 1)

        {

               if (W[here][0] != 0)

                       return W[here][0];

               return INF;

        }

        //메모이제이션

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

        if (result != -1)

               return result;

        result = INF;

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

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

        {

               //이미 방문한 도시

               if (visited & (1 << next) || W[here][next]==0)

                       continue;

               int candidate = W[here][next] + TSP(next, visited + (1 << next));

               result = min(result, candidate);

        }

        return result;

}

 

int main(void)

{

        cin >> N;

        if (N<2 || N>MAX)

               exit(-1);

 

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

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

                       cin >> W[i][j];

 

        int     result = INF;

        memset(cache, -1, sizeof(cache));

        cout << TSP(0, 1) << endl;

        return 0;

}

개발환경:Visual Studio 2017

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