2098-외판원 순회(Bitmask)

2098-외판원 순회

비트마스크DP를 이용한 대표적인 문제이다. 먼저 비트마스크의 원리에 대해서 간단히 설명하자면 숫자를 통해서 메모이제이션 한다는 것이다. 이게 가능한 이유는 컴퓨터에서 정수는 0과 1의 이진수 형태로 저장되기 때문이다. 만약 메모이제이션의 수단으로 배열을 사용하게 된다면 call by reference 방식이므로 함수가 연속해서 호출되는 dfs방식에는 적절하지 않다. 반면에 int자료형은 call by value 방식이므로 함수가 여러번 호출되어도 안정성이 보장된다. 단 비트마스크를 항상 사용할 수 있는 것은 아니고 int형을 사용한다면 int는 32개의 비트로 이루어져 있으므로 n이 그보다 작아야 한다. 일반적으로 '1'은 방문함, 0'은 방문하지 않음으로 통용된다. 비트마스크에서 주로 사용되는 연산은

1. n번째 노드를 1로 바꾸기(check하기) -> next_visited=cur_visited | (1<<n)

2. n번째 노드가 1인지 확인하기 -> if(visited & (1<<n)  (n번째 노드가 1이라면 이 if문이 true이다.)

가 있다. 이 밖에도

3. 모든 노드가 1로 되어있는지 확인하기 -> if(visited==(1<<n)-1)  ( (1<<n)-1은 첫 번째 노드부터 n번째 노드까지 모두 1인 이진수 형태이다.)

아무튼 비트마스크는 배열이 아닌 '정수 한 개'로 메모이제이션을 가능케 한다는 것이 포인트이다.

#include<stdio.h>
#define SIZE 16
#define INF 123456789
int n, start=0;
int dist[SIZE][SIZE], dp[SIZE][1<<SIZE];
//dp[cur][visited]=cost -> 현재위치가(cur)이고 지금까지 visited방문했을때, 남은 점들을 모두 방문하여 시작점으로 돌아가는 최소비용=cost
int fmin(int a, int b) {
    return a > b ? b : a;
}
int path(int cur, int visited) {
    if (visited == (1 << n) - 1) //모든 지점을 다 방문했을때
        return (dist[cur][start]) ? dist[cur][start] : INF;
 
    if (dp[cur][visited] != -1)
        return dp[cur][visited];
 
    dp[cur][visited] = INF;
 
    for (int i = 0; i < n; i++) {
        int next = i;
        int next_visited = visited | (1 << next);
        if (dist[cur][next] == 0) //next로 가는 길이 없다면
            continue;
        if (visited&(1 << next)) //next가 이미 방문한 곳이라면
            continue;
 
        dp[cur][visited] = fmin(dp[cur][visited], path(next,next_visited) + dist[cur][next]);
    }
 
    return dp[cur][visited];
}
int main() {
    scanf("%d", &n);
 
    for(int i=0 ; i<n ; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &dist[i][j]);
 
    for (int i = 0; i < SIZE; i++)
        for (int j = 0; j < (1<<SIZE)-1; j++)
            dp[i][j] = -1;
 
    printf("%d\n",path(0, 1));
 
    return 0;
}