[Algorithm] BOJ 2098 외판원 순회

문제 링크

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

문제 풀이

완전 탐색을 이용해서 해당 문제를 풀 경우, 모든 도시에 대한 순열을 구해서 최소 비용을 탐색해야하는데, 그러면 최악의 경우 16! 만큼의 경우의 수가 나오므로 시간내에 문제를 해결할 수 없다. (주어진 문제의 도시의 수가 최대 16)

주어진 시간 내에 문제를 해결하기 위해 비트마스킹, DP, DFS 모두 이용해야하는 문제이다.

DFS를 이용해 도시를 방문하고, 비트마스킹을 이용해 어느 도시까지 방문했는지 체크하며, 현재 도시에서 최소비용을 구하는데에는 DP가 사용된다.

코드

#include <iostream>
#include <cstring>

using namespace std;

const int MAX = 16;
const int INF = 987654321;
int map[MAX][MAX];
int dp[MAX][1 << MAX];

int n, endBit;

int dfs(int curNode, int curBit) {

    // 모든 도시를 방문 했다면
    if (curBit == endBit)
        // 출발점으로 가는 경로가 있으면 반환하고 없으면 INF 반환
        return map[curNode][0] == 0 ? INF : map[curNode][0];

    // 이미 최소 비용이 계산되어 있다면 반환
    if (dp[curNode][curBit] != -1)      return dp[curNode][curBit];
    dp[curNode][curBit] = INF;

    // 도시 탐방하기
    for (int i=0; i<n; i++) {
        // 가는 경로가 없거나 이미 방문한 도시면 continue
        if (map[curNode][i] == 0)            continue;
        if ((curBit & (1 << i)) == (1 << i)) continue;

        dp[curNode][curBit] = min(dp[curNode][curBit], map[curNode][i] + dfs(i, curBit | 1 << i));
    }
    return dp[curNode][curBit];
}

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

    cin >> n;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> map[i][j];
        }
    }
    endBit = (1 << n) - 1;

    memset(dp, -1, sizeof(dp));
    cout << dfs(0, 1);




    return 0;
}