백준(C) 2098번 [외판원 순회]

외판원 순회 2098번

 

접근방법

DP 풀이법 중에서 비트마스크를 이용한 DP 의 대표적인 문제이다. 외판원 순회 문제는 쉽게 요약하면 한명의

판매원이 모든 도시를 한번씩 방문한뒤 출발지로 돌아오는 최소 비용을 구하는 문제이다.

그냥 일반 DP는 느낌이 누적합, 1,2 차원적 문제의 DP 느낌이라면 비트마스크를 이용한것은 상태가 많은 부분집합의 DP 느낌이다. 

예를 들면 DP의 대표적인 문제인 배낭문제가 무게, 가치 dp[개수][무게]를 이용하여 지금까지 고려한 물건의 수와 무게를 상태로 사용하여 최대 가치를 찾는 것이라면 외판원 순회는 만약 도시가 4곳이라고 가정한다면 dp[1 << 4][4]  첫번째 비트 0 부분에 간곳을 저장해서 여러개의 부분집합의 경우의 수를 나타내는것이다. 1 << 4 는 이진수로 10000 즉 16이다.

0~ 15가 16개 이므로 MAX값은 (1 << 4 ) - 1로 잡는다.그렇다면 사용하는건 0000의 이진수 뿐이다. 이를 바탕으로

방문한 도시를 1 방문하지 않은 도시를 0 이라고 했을때 0000 부터 1111까지의 상태를 이용하여 DP를 진행하면된다.

그렇다면 어떻게 접근해야할지 나온다.

 

일단 dp배열인 dp[1 << n][n]와 도시의 비용인 cost[n][n] 선언한다. dp배열의 첫번째 배열은 방문한 도시를 체크하는 배열이고, 두번째는 마지막으로 방문한 도시이다. cost배열은 n x n의 값을 나타낸다 .

 

반복문의 넣을 조건문은

일단 어떤 도시들을 방문한상태일때 방문한 도시를 제외한 도시에 갔을때 현재의 방문 상태로 도시를 가는 값이 더 작은 값인지, 아니면 다른 경우의 수(다른 방문 상태)로 도시를 가는게 더 작은 값인지 이다.

 

일단 최소값을 구하는 문제는 모든 경우의 수에 최대값을 넣어주고, 첫번째 도시에 방문 표시를 넣어 조건문을 활성화 시킨다. 

 

이 알고리즘에서는 비트 연산을 사용했다. 자주 사용하는 비트 연산은 다음과 같다. 

비트 활성화 : N | (1 << a)

비트 비활성화 : N & ~(1 << a)

비트 반전 : N ^ (1 << a)

비트 확인 : N & (1 <<  a)

 

처음에 이해하는데 시간이 좀 걸렸지만 비트의 상수화(예를 들면 1 << 4 = 16), 비트 검사 비유(고장검사하는 것처럼 일일이 비교 확인하는것으로 생각)를 기준으로 생각을 다르게하니 이해가 바로 됬다. 

비트 마스크는 상태가 복잡한 부분집합 문제에 유리하지만 상태의 개수가 너무 많으면 메모리 및 시간 복잡도 급증하니 조심해야한다. 나같은 경우엔 N > 20 이면 다시 생각해보기로 했다.

 

코드는 다음과 같다.

#include<stdio.h>
#include<stdlib.h>
#define INT_MAX 1000000000

int dp[1 << 17][17];
int cost[17][17];

int main(void)
{


    int n;

    scanf("%d",&n);
    
    for(int a=0;a<n;a++)
    {
        for(int b=0;b<n;b++)
        {
            scanf("%d",&cost[a][b]);
        }
    }

    if(n == 1)
    {
        printf("0\n");
        return 0;
    }

    int end = (1 << n) - 1;

    for(int a=0;a<(1<<n);a++)
    {
        for(int b=0;b<n;b++)
        {
            dp[a][b] = INT_MAX;
        }
    }

    dp[1 << 0][0] = 0;

    for(int a=0;a<(1 << n);a++)
    {
        for(int b=0;b<n;b++)
        {
            if(a & (1 << b))
            {
                if(dp[a][b] == INT_MAX)continue;

                for(int i=0;i<n;i++)
                {
                    if(a & (1 << i))continue;
                    if(cost[b][i] == 0)continue;

                    int next = a | (1 << i);
                    if(dp[a][b] + cost[b][i] < dp[next][i])
                    {
                        dp[next][i] = dp[a][b] + cost[b][i];
                    }
                }


            }
        }
    }


    int ans = INT_MAX;
    for(int a=0;a<n;a++)
    {
        if(cost[a][0] == 0)continue;
        if(dp[end][a]+cost[a][0] < ans)
        {
            ans = dp[end][a] + cost[a][0];
        }
    }


    printf("%d\n",ans);


    return 0;
}