(C++) - 백준(BOJ) 2098 : 외판원 순회

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

2098번: 외판원 순회

dp 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

 1. n, 도시로 가는 비용 cost, d배열을 선언합니다. 2. n입력 후, n행, n열만큼 i -> j도시로 가는 비용들을 cost에 입력합니다.

 

📔 풀이과정

n이 16인 경우 도시의 경로는 16!로 매우 많습니다. 16개의 도시를 순열로 배열하는 것과 같기 때문입니다. 도시의 상태를 빠르게(O(1)) 알기 위해 bit masking을 이용해야 합니다. 또한 dp를 이용해 갈 수 있는 도시를 확인해가며 최종적으로 다시 돌아오도록 구현해야 합니다. d배열을 2차원으로 선언해 cur도시를 경로를 정했을 때 status에 대한 cost값이라고 정의합니다. d[cur][status]로 표시됩니다.

 

 dp함수를 수행합니다.

 1. 0번 도시부터 확인합니다. 0번도시는 bit로 표현한다면 0.....01입니다. bit의 자리수를 확인했을 때 x번째 도시를 경로로 정했는지의 유무를 알 수 있도록 합니다. x번째 도시를 들르기로 했다면 x번째 bit을 1로 켜줍니다. 이런식으로 모든 도시에 대한 확인을 마쳤다면 모든 도시의 bit이 켜져있을 것이고 그 때 목적지에 대한 값을 반환해줌으로써 0번으로 다시 돌아오는 cost를 합쳐 전체 경로의 cost를 구할 수 있습니다. 하지만 다시 돌아오는 경로가 0인 경우에는 갈 수 없으므로 INF를 반환하도록 합니다. 이는 기저 case가 됩니다. 

 

 2. 현재 level cur번 도시에서 next번 도시로 가는 경우에 대해 dp함수를 재귀적으로 호출해 가장 적은 값을 반환합니다. 

이 때 cur번 도시에서 next번 도시로 가는 경로가 있어야하며(cost[cur][next]) 이미 경로로 정한 도시면 안됩니다. bitmasking한 변수를 status라고 정의했기 때문에 O(1)만에 정한 도시인지 아닌지를 &연산으로 구할 수 있습니다. 이렇게 뻗어나갔을 때 최종 cost들 중 최솟값을 ret에 저장해줍니다.

 

 

📔 정답출력

 dp함수의 결과값을 반환합니다.

---

📕 Code

Top down

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int n, cost[16][16], d[16][1 << 16];

int dp(int cur, int status){
    if(status == (1 << n) - 1){
        if(cost[cur][0] == 0) return INF;
        return cost[cur][0];
    }
    int &ret = d[cur][status];
    if(ret != -1) return ret;
    ret = INF;
    for(int next = 0; next < n; next++){
        if(!cost[cur][next]) continue;
        if((status & (1 << next)) == (1 << next)) continue; //이미 정했던 도시면
        ret = min(ret, cost[cur][next] + dp(next, status | 1 << next));
    }
    return ret;
}

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