(c++) 2098번: 외판원 순회 비트마스크

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

2098번: 외판원 순회

 

 

 

문제 개요

 

 

유명한 문제인 외판원 순회는

다익스트라 알고리즘에서 많이 등장했던 문제이다.

 

해당 문제의 취지는 비트마스크와 동적계획법을 사용하여 해결하는 방법으로 푸는 것이다.

 

비트마스크는 해당 도시의 방문 여부를 파악하는 용도로 사용하면 된다.

 

문제의 테스트케이스는 무조건 순회하는 방법으로 나오기에 순회가 안 되는 상황은 고려하지 않아도 된다.

그리고 첫 번째 도시에서 출발하는 경우만 고려해주어도 각 도시에서 시작하는 경우와 똑같다.

 

시작 도시도 방문한 것이기에 방문 처리를 미리 해두어야 한다.

 

 

 

코드

 

 

2퍼센트에서 실패하는 경우는 동적계획법을 이용할 때 사용하는 캐시를 double형을 사용했을 경우이다.

변수형을 고려해주자.

#include <bits/stdc++.h>
#define MAX 16
#define INF 1e9;
using namespace std;

int n, dist[MAX][MAX];
int cache[MAX][1<<MAX];

int minCost(int here, int visited) {
    // 모든 도시 돌 경우 시작 위치로
    if (visited == (1<<n)-1) {
        if (dist[here][0] == 0) {
            return INF;
            }
        else return dist[here][0];
    }
    int& ret = cache[here][visited];
    if (ret != -1) return ret;
    ret = INF;
    for (int next = 0; next < n; next++) {
        // 이미 방문한 도시는 넘어감 / 0인 경우도 넘어감
        if (visited & (1<<next) || dist[here][next] == 0) continue;
        ret = min(ret, dist[here][next] + minCost(next, visited | (1<<next)));
    }
    return ret;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
        }
    }
    fill(&cache[0][0], &cache[MAX-1][1<<MAX], -1);
    // 0번 노드 시작시 0번 노드 방문 처리
    cout << minCost(0, 1<<0);
}