[백준 2098] 외판원 순회

 

알고리즘을 배우다보면 피할 수 없이 만나는 tsp문제이다.

이 문제의 입력인 N의 크기가 최대 16으로 극히 작은 문제이기 때문에

dp를 이용하여 문제를 풀 수 있다.

 

하지만 dp 사용에 있어서 tsp(currentCity, visited) 를 나타낼 때 visited를 배열(벡터)를 사용하기가 어려워진다.

메모이제이션을 해야하는데 visited 를 통째로 메모하기도 어렵고 공간 복잡도도 굉장할 것이다.

 

그래서 N이 작기때문에!!!!! 할 수 있는 방법으로 비트마스크를 사용한다.

0번째 도시를 이미 갔다. == 0번째 비트가 1

0번째 도시를 아직 안갔다. == 0번째 비트가 0

이런식으로 0번째부터 n-1번째 도시까지 총 n개의 도시를 비트로  체크할 수 있다.

 

여기서 메모이제이션을 위한 배열은 다음과 같이 만들었다.

int memo[MAX_SIZE][1 << MAX_SIZE]; 

일단 앞의 인덱스로 현재 방문중인 도시를 표현하고 뒤의 값은 비트마스크 값으로 visited를 의미한다.

 

이 문제에서는 비트마스크 연산 3가지가 중요하다.

• 해당 자리 비트가 1인지 확인.
• 해당 자리 비트를 1로 설정.
• 해당 자리 비트를 0으로 설정.

위의 3가지 연산은

2019/08/06 - [PS/Tip] - [비트연산] 비트연산자 & 비트마스크

[비트연산] 비트연산자 & 비트마스크

이곳에 정리해뒀다.

---

무튼 코드는 다음과 같다.

 

#include <iostream>
#include <cstring>
using namespace std;

const static int INF = 987654321;
int n;
int map[16][16];
int memo[16][1<<16];

int tsp(int currentCity, int visited){
    int& ret = memo[currentCity][visited];
    if(ret!=-1) return ret;
    
    // base case : 모든 도시를 다 방문함 == 모든 도시가 1임.
    if(visited == (1<<n)-1){
        // 0번째 도시로 다시 돌아감. (싸이클)
        if(map[currentCity][0] != 0) return map[currentCity][0];
        else return INF;
    }
    
    ret = INF;
    for(int i = 0; i < n; i++){
        // 가는 길이 있고 방문한 적 없으면 가라
        if(map[currentCity][i] && !(visited & (1 << i))){
            int visit = visited | (1 << i); // 간다
            ret = min(ret, tsp(i, visit) + map[currentCity][i]);
        }
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j++)
            cin >> map[i][j];
    }
    memset(memo, -1, sizeof(memo));
    cout << tsp(0, 1) << '\n';
    
    return 0;
}