[BOJ] 백준 2098 외판원 순회

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

Approach

※ 비트마스크 (Bitmask) 

비트마스크 (Bitmask)

완전 탐색으로 접근하는 경우 TLE 발생.

▶ 동적 계획법과 비트마스크 활용.

 

비트마스크를 이용해 방문한 노드를 표시합니다.

ex) 0번과 2번 도시를 방문하였다면 → 0101 표시 

        → 배열로는 십진법으로 표현하기에 22 + 20 = 5

즉, 어느 도시를 방문했는지를 저장하기 위함.

모든 도시를 방문했다면 1111 = 24 - 1 = 15

 

dp[here][visited] = 현재 위치가 here이고, visited 도시까지 방문했을 때 최소값

최소 비용이 드는 경로가  0 → 1 → 2 → 3 → 4 → 0 이든 2 → 3 → 4 → 0 → 1 → 2 이든 동일하므로

임의로 출발점을 0번 도시로 설정.

결과적으로 0번 도시를 시작으로 다른 도시를 모두 방문하여 다시 0번 도시로 돌아와야 합니다.

---

#include<iostream>
#include<cstring>
using namespace std;
#define INF 987654321
#define MAX 16
#define MIN(a, b)(a < b ? a : b)
 
int N;
int cost[MAX][MAX];
int dp[MAX][1 << MAX];
 
int DFS(int here, int visited){
    // 모든 도시를 방문한 경우
    if (visited == (1 << N) - 1){
        // 방문한 마지막 도시에서 0번 도시로 다시 돌아갈 수 있는지 확인
        if (cost[here][0] == 0)
            return INF;
        return cost[here][0];
    }
 
    // 이미 방문한 도시인 경우
    if (dp[here][visited] != -1)
        return dp[here][visited];
    
    dp[here][visited] = INF;
    
    for (int next = 0; next < N; next++){
        // 경로가 없는 도시인 경우
        if (cost[here][next] == 0) continue;
        // 이미 방문한 도시인 경우
        if (visited & (1 << next) > 0) continue;
        // 현재 도시(here)에서 방문한 도시들(visited)일때 도시 전체를 순회한 최소 비용.
        dp[here][visited] = MIN(dp[here][visited], cost[here][next] + DFS(next, visited | 1 << next));
    }
 
    return dp[here][visited];
}
 
 
int main(void){
    cin >> N;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            cin >> cost[i][j];
        }
    }
    
    memset(dp, -1, sizeof(dp));
    cout << DFS(0, 1) << endl;
}