[BOJ 2098] 외판원 순회

문제출처

https://www.acmicpc.net/problem/2098

문제풀이

/**
 * n이 16까지 주어지는데 모든 경우의 수는 16!로 굉장히 큰 것을 예상할 수 있습니다.
 * => 처음 1번도시를 방문하고 다음도시를 방문할 수 있는 경우의 수는 n-1이며 그 다음은 n-2이기 때문에 n!의 시간복잡도를 가집니다.
 * 처음에 dfs와 같은 방법으로 전체탐색을 수행하려 했지만 시간제한이 1초여서 다른 방법을 생각하던 중
 * DP를 사용하면 해결될듯 하여 해당 주제인 비트마스크와 DP를 사용했습니다.
 *
 * 비트마스크 visit로 사용
 * 만약 4개의 도시중 방문한 도시가 없다면 0000으로 표현할 수 있습니다. 1번 도시를 방문한 경우 0001
 * 2번도시를 방문한 경우는 0010 이와 같이 1번 3번도시를 방문했다면 0101으로 표현할 수 있습니다.
 * 때문에 모든 도시를 방문한 경우 1111로 나타낼수 있습니다.
 * 여기서 중요한 것은 하나하나의 비트가 0이면 방문하지 않은 상태를 뜻하고 1이면 방문한 것을 의미합니다.
 *
 * 그럼 방문여부를 체크할때는 어떻게 할까 고민해 봐야한다. 예제에서 볼 수 있듯이 1->3의 값과 3->1의 가중치가 다릅니다.
 * 즉, 현재 출발도시도 중요한 영향을 미치며 방문여부도 값에 영향을 미치는 것을 알 수 있습니다.
 * 이를 통해 dp배열의 구조를 생각할 수 있습니다. dp[현재도시][방문한도시]와 같이 표현할 수 있습니다.
 * 예를 들면 1,2,3번 도시를 방문했고 현재 3번도시에 위치한 경우 최소거리를 dp[3][0111](dp[3][7])로 나타낼 수 있습니다.
 * 여기서 레퍼런스 변수 &ret을 사용했는데 dp배열을 사용해도 문제없습니다. 레퍼런스 변수는 dp배열의 인덱스값을 확실하게 참조할 수 있는
 * 장점이 있습니다. 레퍼런스 변수 자체가 참조하는 주소를 기억하기 때문에 더 안정적이라고 하네요.
 * 이 문제는 0번도시, 4번도시 아무도시에서 시작해도 항상 같은 값을 가집니다. 왜냐하면 사이클이기 때문이죠.
 * 만약 경로가 있다는 가정하에 1->2->3->4->1 의값은 2->3->4->1->2 의 값과 같습니다. 2의 왼쪽은 1 // 2의오른쪽은 3 이런식으로 비교하면
 * 사이클이므로 값이 같다는 것을 알 수 있습니다. 때문에 저는 0번도시에서 시작을 하는 것으로 풀이를 시작했습니다.
 * (다시 한번 강조하지만 어떤 도시든지 상관이 없습니다.)
 *
 * INF값을 0x7fffffff값을 주었는데 이경우 시간초과가 떴습니다. 왜 시간초과인지는 모르겠지만 1만 더해도 int범위를 벗어나기 때문에
 * 문제가 있을것이라 생각하고 10억이 넘는값으로 수정하니 맞았습니다.
 */

소스코드

#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAX 16
 
using namespace std;
 
int n;
int map[MAX][MAX];
int dp[MAX][1<<MAX];
 
int tsp(int cur, int visit) {
    //방문한 곳은 재방문하지 않았으므로 다시 원점으로 돌아오는 가중치를 return해줘서 더해준다.
   if(visit == (1<<n)-1)
       return (map[cur][0]>0) ? map[cur][0] : INF;
   int &ret=dp[cur][visit];
   if(ret>0)   return ret;
   ret=INF;
   for(int i=0; i<n; i++) {
       if(!(visit & (1<<i)) && map[cur][i]>0) {
           ret=min(ret, tsp(i, visit|(1<<i)) + map[cur][i]);
       }
   }
   return ret;
}
 
int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    cin>>n;
    for(int i=0; i<n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
    cout<<tsp(0,1)<<endl;
    return 0;
}