BOJ 2098 외판원 순회 (비트필드를 이용한 다이나믹 프로그래밍)

백준 BOJ 2098번 : 외판원 순회

Solved.ac 난이도 : Gold I

알고리즘 분류 : 비트필드를 이용한 다이나믹 프로그래밍

 

외판원 문제란, 도시의 수 N(≤ 16)에 대해 도시에서 도시로 가는 비용들이 주어질 때, 모든 도시를 순회하고 돌아오는데 필요한 최소 비용을 구하는 문제입니다.

 

 

 

dp를 이용하여 이 문제를 해결하기 위해서는, 각 도시에 대한 방문 여부를 저장해야 합니다.

따라서 메모리를 효율적으로 사용하기 위해 비트필드를 사용한 다이나믹 프로그래밍으로 문제를 해결해야 합니다.

 

dp[i][j]를 현재 도시가 i이고 j의 방문 상태를 가질 때, 최소 비용으로 정의합니다.

이 때 방문 상태 j란 각 비트에 대해 해당 비트가 1이라면 해당 번호의 도시를 방문한 것이고 0이라면 방문하지 않은 것입니다.

예를 들어 N = 4이고 j = 0111(2)이라면, 0, 1, 2번 도시를 방문한 상태를 의미합니다.

ex ) dp[2][7] = dp[2][0111(2)] : 0, 1, 2번 도시를 방문하고 현재 2번 도시까지 왔을 때 드는 최소 비용

 

이제 점화식만 세우면 됩니다.

next를 다음 방문할 도시라고 하고, next = 0 ~ N-1에 대해 dp[curr][status] = min(dp[curr][status], cost[curr][next] + dp[next][status | (1 << next)]으로 세워주면, 더 낮은 비용으로 현재 dp 값을 가질 때 갱신이 되므로 최소 비용을 구할 수 있게 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;

const int MAX = 16;
const int INF = 20000000;

int N;
int cost[MAX][MAX], dp[MAX][1 << MAX];

int DP(int curr, int status) {
    if(status == (1 << N) - 1) {
        if(cost[curr][0] == 0) return INF;
        return cost[curr][0];
    }

    if(dp[curr][status] != -1) return dp[curr][status];

    dp[curr][status] = INF;
    for(int i=0; i<N; i++) {
        int next = i;

        if(cost[curr][next] == 0) continue;
        if((status & (1 << next)) == (1 << next)) continue;

        dp[curr][status] = min(dp[curr][status], cost[curr][next] + DP(next, status | (1 << next)));
    }

    return dp[curr][status];
}

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

    cin >> N;

    memset(dp, -1, sizeof(dp));

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) cin >> cost[i][j];

    cout << DP(0, 1) << "\n";
}

 

 

---

+ 추가로 아래의 문제도 같은 코드로 해결이 가능합니다.

백준 BOJ 10971번 : 외판원 순회 2

Solved.ac 난이도 : Silver I

 

이 문제는 N ≤ 10에 대한 외판원 순회 문제입니다.

N이 10 이하라면 브루트포스 알고리즘과 백트래킹을 활용하여 문제를 해결할 수 있으나, 위의 문제의 축소판이므로 비트필드를 활용하여 더욱 효율적으로 풀이가 가능합니다.

따라서 위의 문제와 동일한 코드를 제출해주면 정답 처리를 받을 수 있습니다.