[boj] 백준 2098 외판원 순회 (c++) - TSP(비트마스킹, dp, dfs)

[문제]

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

2098번: 외판원 순회

 

[풀이]

TSP(Traveling Salesperson Problem)이라는 외판원 순회 알고리즘이 따로 존재할 정도로 유명한 문제라는데...처음 봤다. 비트마스킹도 익숙치 않아서 여러 블로그 깨작거리면서 갱신히 풀었다. 알고리즘 카테고리에 한 번 정리해야 할 것 같다.

TSP는 어떠한 도시에서 출발하여 다른 모든 도시들을 거쳐 출발 했던 도시로 다시 돌아오는데 드는 최소 비용을 찾는 문제이다. 비트마스킹과 dp를 이용하고(여기서는 도시의 개수가 최대 16개이므로 dp를 이용해야 함) dfs에 적용하면 된다.

TSP 알고리즘 정리하면서 자세히 다시 보겠지만, 초점을 맞춰야 할 부분 2가지를 얘기하자면

1) 어차피 사이클이 생기기 때문에 어디서 출발하는지는 상관없다. 출발 도시로 돌아와야 하는데 만약 1 -> 3 -> 4 -> 5 -> 2 -> 1이 최소 비용을 갖는 경로라고 가정해보면 3 -> 4 -> 5 -> 2 -> 1 -> 3 이나 4 -> 5 -> 2 -> 1 -> 3 -> 4 나 시작 도시만 다를 뿐 어차피 같은 경로이다. 따라서 다 최소비용을 가질거니까 출발도시를 1번으로 고정시키고 생각할 수 있다.

2) 중복 문제를 해결하기 위해 DP(메모이제이션)를 사용한다. dp[current][visited]는 current: 현재 도시, visited 방문했던 도시(비트마스킹)들 상태에서 순회를 마치는데 드는 최소 비용을 저장해 사용한다.

 

코드를 좀 더 자세히 보면,

 

    if(visited == ((1 << n) - 1)){ //모든 도시를 방문한 상태, 2^n - 1
        if(w[current][0] != 0){ //current에서 0번째 인덱스로 돌아갈 수 있는지
            return w[current][0];
        }
        else
            return INF;
    }

 

만약 n이 5라면 모든 도시를 방문한 상태는 2^5 - 1 = 11111 = 31 이다. 이는 (1 << 5) - 1인 100000 = 2^5 - 1 =31과  같다. 따라서 방문한 도시들 상태 visited가 (1 << n) - 1과 같다면 모든 도시를 방문한 상태이다. 이 때, current에서 출발 도시인 0으로 가는 길이 있다면(w[current][0]이 0이 아니라면) w[current][0]를 반환하고 없다면 해당 경로를 무효화하기 위해 INF를 반환한다.

 

    if(dp[current][visited] != -1)
        return dp[current][visited];

 

메모이제이션 부분이다. 해당 dp 값이 존재한다면(처음에 -1로 초기화했으므로 -1이 아니라면) 반환해준다.

 

 dp[current][visited] = INF;

    for(int i=0; i<n; i++){
        if((visited & (1 << i))|| w[current][i]==0){ //i번째 도시를 이미 방문을 했거나, current에서 i로 가는 길이 없을 때
            continue;
        }
        dp[current][visited] = min(dp[current][visited], w[current][i] + dfs(i, visited | 1 << i)); //dp 갱신
    }

 

해당 dp 값이 없다면 INF로 값을 넣어주고(처음부터 INF로 초기화할 걸) dp를 갱신해준다. 

visited & ( 1<< i ) 는 i 번째 도시를 이미 방문한 경우를 걸러주기 위함이다. 만약 visited가 10110 이라면 첫번째 도시에 대해서는 10110 & 00001 이므로 0, 즉 false이다. visited 경로에 첫번째 도시가 없음, 아직 방문하지 않았음을 알 수 있다. 반면 두번째 도시의 경우 10110 & 00010 이므로 1, true이다. visited 경로에 두번째 도시가 있어 이미 방문했음을 나타내기 때문에 고려해주지 않는다.

w[current][i] == 0 인 경우는 current에서 i번째 도시로 가는 길이 없는 경우이므로 역시 제외한다.

이제 dp를 갱신해준다. visited | 1 << i 는 visited 경로에 i번째 도시를 추가해주는 것이다. 

 

 

[코드]

 

#include <iostream>
#include <vector>
#include <cstring>

#define MAX 16
#define INF 987654321

using namespace::std;

int n; //도시의 수 n개
int w[MAX][MAX]; //도시 i에서 j로 가기 위한 비용
int dp[MAX][1 << MAX]; //i: 현재 방문 도시, j: 지금 까지 지나온 경로(비트마스킹) 일 때 최소 비용을 저장,

int dfs(int current, int visited){
    if(visited == ((1 << n) - 1)){ //모든 도시를 방문한 상태, 2^n - 1
        if(w[current][0] != 0){ //current에서 0번째 인덱스로 돌아갈 수 있는지
            return w[current][0];
        }
        else
            return INF;
    }

    if(dp[current][visited] != -1)
        return dp[current][visited];

    dp[current][visited] = INF;

    for(int i=0; i<n; i++){
        if((visited & (1 << i))|| w[current][i]==0){ //i번째 도시를 이미 방문을 했거나, current에서 i로 가는 길이 없을 때
            continue;
        }
        dp[current][visited] = min(dp[current][visited], w[current][i] + dfs(i, visited | 1 << i)); //dp 갱신
    }

    return dp[current][visited];
}

int main() {
    cin >> n;

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> w[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));

    //외판원 순회에 필요한 최소 비용 출력
    cout << dfs(0, 1);


}