[c++] 백준 2098 외판원 순회 (Traveling Salesman problem /TSP / 비트마스킹 / bitmasking)

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

외판원 순회 / Traveling Salesman problem

여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것.

조합 최적화(Combinatorial Optimization) 문제로 각 변에 가중치가 주어진 완전그래프에서 가장 작은 가중치를 가지는 '해밀턴 순환'을 구하는 'NP-난해'에 속하는 문제

Solution

비트마스킹을 이용한 dp

DP사용이유를 설명하자면 메모리와 시간복잡도때문. n이 10이하인 경우는 브루트 포스(brute force)를 이용하여 구할 수 있다. 그러나 n이 16이하인 경우는 dp를 이용하여 중복 계산을 방지해주어야 한다.

비트마스킹을 이용하여 방문 상태를 표시할것이다. 비스마스킹을 사용하는 이유는, 각 정점마다 다른 모든 정점들의 방문상태를 표시해야하기 때문에 메모리를 줄이기 위해 사용한다.

대충 말 하자면 걍 dfs랑 비슷하다.

핵심 : dp[현재 방문도시][방문한 도시 (비트마스크)]에 경로값을 저장한다.

비트마스킹

정수의 이진수표현을 자료구조로써 쓰는 방법.
장점 : 빠른 실행시간, 보다 적은 메모리, 깔끔한 코드

비트연산자

사용한 연산자만 간단히 정리하자면

a&b

a의 모든 비트와 b의 모든 비트를 AND연산

a|b

a의 모든 비트와 b의 모든 비트를 OR연산

선언부

#define INF 987654321;
int n,map[16][16];
int dp[16][1<<16]; //각 마을이 방문한 도시를 2진법으로 저장

INF를 987654321로 잡았다. 더하는 연산이 있다보니 21억으로하면 오버플로우 난다. (틀렸었던 이유)
map은 이동하는 비용, dp는 총 비용

dp배열 초기화

memset(dp, -1, sizeof(dp)); //dp배열 -1로 초기화

map배열을 입력받고 dfs를 실행하기 전, dp배열을 모두 -1로 초기화한다. 방문여부를 파악하기 위함이다.

dfs

문제 조건에서 항상 순회할 수 있는 경우만 입력으로 주어진다. 라고 제시를 해주었기때문에 dfs한바퀴만 돌려도 정답이 나온다.

int dfs(int cur, int visit)

dfs는 현재 도시 cur과 지끔까지 방문한 도시 visit을 받는다.

if (visit == (1<<n)-1){ //탐색 완료
        if(map[cur][0] == 0) //이동불가능
            return INF;
        return map[cur][0];
    }

 (1<<n)-1는 모든도시들의 방문 여부입니다. 참고로 1이 n개 (111~)

if (dp[cur][visit] != -1) //이미 탐색했으면
       return dp[cur][visit];
   
   dp[cur][visit] = INF;

처음에 입력받고 dfs 실행 전에 memset을 이용하여 전부 -1로 초기화 해놓았기 때문에, -1일때만 탐색

for (int i=0; i<n; i++){
        if (map[cur][i]==0) //길 X
            continue;
        if ((visit & (1<<i)) == (1<<i)) //이미 방문
            continue;
        dp[cur][visit] = min(dp[cur][visit], map[cur][i] + dfs(i, visit | 1<<i));
    }
    
    return dp[cur][visit];

가장 중요한 부분!!
먼저 해당하는 도시로 갈 수 있는지 확인 하고 방문 여부를 파악한다.
그 다음이 핵심인데 처음시작 -> 현재도시 로 가는 거리와 현재도시 -> 방문하지않은 다른 도시로 가는 거리 중 작은것을 dp배열에 저장한다.
여기서 visited | (1<<i)를 사용하는 이유는 현재도시를 방문했다는 의미에서 사용한다.

전체코드

#include <iostream>
#include <cstring>
using namespace std;

#define INF 987654321;

int n,map[16][16];
int dp[16][1<<16]; //각 마을이 방문한 도시를 2진법으로 저장

int dfs(int cur, int visit){
    
    if (visit == (1<<n)-1){ //탐색 완료
        if(map[cur][0] == 0) //이동불가능
            return INF;
        return map[cur][0];
    }
    
    if (dp[cur][visit] != -1) //이미 탐색했으면
        return dp[cur][visit];
    
    dp[cur][visit] = INF;
    
    for (int i=0; i<n; i++){
        if (map[cur][i]==0) //길 X
            continue;
        if ((visit & (1<<i)) == (1<<i)) //이미 방문
            continue;
        dp[cur][visit] = min(dp[cur][visit], map[cur][i] + dfs(i, visit | 1<<i));
    }
    
    return dp[cur][visit];
}

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    cin>>n;
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            cin>>map[i][j];
        }
    }
    
    memset(dp, -1, sizeof(dp)); //dp배열 -1로 초기화
    cout<<dfs(0,1);
    
    return 0;
}

틀린 이유 첫번쨰는 cstring 미선언, 두번째는 INF 오버플로우