[BOJ] 백준 2098 외판원 순회

문제 링크

www.acmicpc.net/problem/2098

2098번: 외판원 순회

 

풀이

1) 어떤 정점에서 시작하든 최소 비용은 같습니다. 그러니 0번부터 조집시다.

A->B->...->F->A

B->C->...->A->B

모두 같습니다.

 

2) 현재까지 어느 정점들을 탐색해왔는지 비트 마스킹으로 관리합니다. 그 집합과 현재 정점을 기준으로 dp를 전개합니다. 다음으로 이동할 정점을 고를 때 집합에 포함되지 않는 정점을 고르면 됩니다.

 

3) 기저 사례는 $(n-1)$번까지의 모든 비트가 1인 경우입니다. 이때 마지막 정점에서 0번 정점으로 갈 수 있는지를 확인해 적절한 값을 리턴해줍시다.

 

 

정답 코드

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
using namespace std;

int d[1 << 17][22];
int p[22][22], n;

int go(int s, int now) {
    if (s == ((1 << n) - 1)) {
        return p[now][0]? p[now][0] : INF;
    }
    int &ret = d[s][now];
    if (ret != -1) return ret;
    ret = INF;
    for (int next = 1; next < n; next++) {
        if (s & (1 << next)) continue;
        if (p[now][next] == 0) continue;
        ret = min(ret, go(s | (1 << next), next) + p[now][next]);
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    memset(d, -1, sizeof(d));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> p[i][j];
        }
    }
    cout << go(1, 0);
}