백준 2098 (외판원 순회) c++

문제

2098번: 외판원 순회

n개의 도시들이 주어지고 도시와 도시간의 이동비용을 알려주고 임의의 시작점에서  모든 도시들을 순회하는데 최소의 금액으로 순회하는 비용을 출력하는 문제입니다.

도시와 도시간의 이동은 쌍방향이고 1번도시에서 2번도시로 갈때의 비용과 2번도시에서 1번도시로 갈때의 비용은 

서로 다릅니다. 또한 한번 방문한 도시는 다시 방문할 수 없고 마지막으로 방문했던 도시는 맨 처음 도시로 돌아와야 합니다.

 

먼저 n의 범위가 최대 16으로 주어졌는데 이를 단순히 backtracking 방식으로 접근하면 최악의 경우 

16! 의 경우의 수가 나올 수 있으므로 이는 불가능합니다.

따라서 bit dp방식을 이용하였는데 예를 들어 1번째 도시와 3번째 도시를 방문하였다면 0000000000000101 로 표현

가능합니다.

이를 이용해서 문제를 접근하였습니다.

 

long long cost[17][17];
long long dp[1 << 17][17];

cost배열은 2차원 배열로 각 도시마다 이동에 따른 비용을 저장하는 배열입니다.

dp배열을 보면 다음과 같습니다.

dp[n][i] = n의 켜져있는 bit의 도시를 모두 방문했고, 마지막으로 방문했던 도시가 i일때 최소비용 입니다.

따라서 [1 << 17] 이면 실제 배열은 17개의 bit를 사용할 수 있습니다.

for (int ii = 0; ii < n; ii++) {
        for (int i = 1; i < (1 << n); i++)
            for (int j = 0; j < n; j++)dp[i][j] = inf;
        dp[(1 << ii)][ii] = 0; //ii 번째 bit만 켜져있고 마지막 방문정점이 ii일때만 0이 된다 (시작 정점이기 떄문) 
        for (int i = 0; i < (1 << n); i++) {
            for (int j = 0; j < n; j++) {
                if (!(i & (1 << j)))continue; //dp[i][j]에서 i와 j가 같지 않다면 continue
                for (int k = 0; k < n; k++) { //dp[i][j]가 같을 때 현재 위치는 j이므로 j에서 k로 가는 dp 업데이트
                    //j->k로 가는 간선
                    if (!cost[j][k] || (i & (1 << k)))continue;
                    x = i | (1 << k); //i의 k번째 bit를 켜줌
                    dp[x][k] = min(dp[x][k], dp[i][j] + cost[j][k]);
                }
            }
        }
        for (int i = 0; i < n; i++)if (cost[i][ii])ans = min(ans, dp[(1 << n) - 1][i] + cost[i][ii]);
    }

1번째 for문은 첫 시작점을 선택하는 반복문입니다. ii가 n까지 순회하면서 시작점을 어디로 잡으냐에 따라 비용이 달라집니다.

2, 3번 째 for문은 dp배열을 inf로 초기화 해주는 과정입니다.

4번째 줄은 시작 정점을 설정해주고 그 시작점은 dp가 0이 됩니다.(ii번째 bit만 켜져있고 마지막으로 방문정점이 ii이기 때문)

이제 5번째 줄 ~ 16번째 줄까지 모든 도시들을 순회할 것입니다. 

dp[i][j] 일때 k로 갈 수 있는지 확인할 것입니다.

7번째 줄의 의미는 켜져있는 bit와 한개라도 중복되지 않는 다면 continue한다는 의미입니다.

continue에 안걸리는 i와 j를 보시면 이해가 가실겁니다. 예를 들어 n이 4라면

(i , j)          i           1<<j

(1, 0)       0001        0001

(2, 1)       0010        0010

(3, 0)       0011        0001

(3, 1)       0011        0010

(4, 2)       0100        0100 

.

.

.

.

따라서 dp[i][j]일 때 dp[j][k]로 갈 수 있느냐로 판단 할 수 있습니다.

10번째 줄을 보시면 만약 j에서 k로 가는 간선이 없거나 또는 k가 이전에 방문했다면 continue를 하면 됩니다.

11번째 줄을 보시면 i의 k번째 bit를 켜주는 코드 입니다.

16번째 줄을 보면 이제 마지막 도시까지 순회를 완료하고 맨 처음에 시작했던 도시로 가는 간선이 존재한다면 

ans를 업데이트 하는 과정입니다.

(1 << n ) - 1 의미는 n개의 bit가 모두 켜져있는 상태 입니다.

예를 들어 n이 4이면 (1 << 4) - 1 이므로 15가 되는데 15는 이진수로 표현하면 1111 입니다.

 

위 코드의 시간복잡도는 O(2^N * N^2)

시작정점을 ii로 전부 탐색할 필요가 없는데, 1이라는 정점을 시작정점으로 해도 사이클이 생기기 때문에, 시작 정점을 하나로 고정해도 모든 경우를 탐색할수 있어서 O(2^N * N)으로 최적화가 가능합니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf LONG_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll cost[17][17];
ll dp[1 << 17][17];
ll n, ans;
ll x;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> cost[i][j];
    ans = inf;
 
    for (int ii = 0; ii < n; ii++) {
        for (int i = 1; i < (1 << n); i++)
            for (int j = 0; j < n; j++)dp[i][j] = inf;
        dp[(1 << ii)][ii] = 0; //ii 번째 bit만 켜져있고 마지막 방문정점이 ii일때만 0이 된다 (시작 정점이기 떄문) 
        for (int i = 0; i < (1 << n); i++) {
            for (int j = 0; j < n; j++) {
                if (!(i & (1 << j)))continue; //dp[i][j]에서 i와 j가 같지 않다면 continue
                for (int k = 0; k < n; k++) { //dp[i][j]가 같을 때 현재 위치는 j이므로 j에서 k로 가는 dp 업데이트
                    //j->k로 가는 간선
                    if (!cost[j][k] || (i & (1 << k)))continue;
                    x = i | (1 << k); //i의 k번째 bit를 켜줌
                    dp[x][k] = min(dp[x][k], dp[i][j] + cost[j][k]);
                }
            }
        }
        for (int i = 0; i < n; i++)if (cost[i][ii])ans = min(ans, dp[(1 << n) - 1][i] + cost[i][ii]);
    }
    cout << ans;
    
    return 0;
}