[BOJ 2098] 외판원 순회(비트마스크, 자세한 설명)

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

2098번: 외판원 순회

 

 

이 문제는 다이나믹 프로그래밍 분류이다.

 

 

 

 

다이나믹 프로그래밍의 본질은 소문제의 해결 방법을 이용해서 대문제를 해결하는 것이다.

 

 

 

 

i번째에 방문되는 도시들과 i + 1번째 방문되는 도시들간의 관계를 정의해보자.

 

 

 

 

i번째 방문되는 도시들의 집합을 A, i + 1번째 방문되는 도시들의 집합을 B라고 하자.

 

 

 

 

B가 될 수 있는 조건은 무엇일까?

 

 

 

 

1. A에서 B까지 경로가 존재해야 함.

2. 방문되지 않은 도시

 

 

 

 

위의 두 가지 조건을 만족해야 한다.

 

 

 

 

1번은 쉽게 주어진 문제의 조건을 이용해서 구할 수 있다.

 

 

 

 

2번을 구하기 위해서는, 방문된 도시들을 기억해둘 필요가 있다. 이 때 비트마스크가 필요하다.

 

 

 

 

비트마스크를 필요한 이유를 좀 더 자세히 설명하자면, 만약에 비트마스크를 사용하지 않고 단순히 방문을 체크하는 배열만 이용했다고 가정해보자.

 

 

 

 

이 때, 메모이제이션을 사용하지 않으면, 시간초과가 발생한다.

 

 

 

 

따라서, 메모이제이션을 사용하기 위해 매개변수를 사용하게 될 것이다. 이 때, 배열을 통해서 사용한다면, 들어갈 수 있는 매개변수는, 현재 방문도시와 몇 번째 도시인지 2가지정도이다.

 

 

 

 

x1 = 현재 방문도시

x2 = 몇 번째 방문도시인지

 

 

 

 

DP[x1][x2]에 값이 들어간다면, 지금까지 어떻게 방문된 도시들을 전혀 반영하지 못하기 때문에, 틀린 답이 나오게 된다.

 

 

 

 

x1 = 현재 방문도시

x2 = 지금까지 방문된 도시(비트마스크)

 

 

 

 

이렇게 정의한다면, 지금까지 방문된 도시들을 손쉽게 반영할 수 있다.

 

 

 

 

비트마스크는,

 

 

 

 

총 5개 도시가 있을 때,

 

 

 

 

1번과 3번 도시를 방문했다면 = 00101

2번과 4번 도시를 방문했다면 = 01010

모든 도시를 방문하지 않았다면 = 00000

 

 

 

 

위의 형태로 표현하는 것이다. 비트를 사용하기때문에, 십진수로 변환해도 값이 적은 장점이 있다.

 

 

 

 

위의 관계를 코드로 나타내면 아래와 같다.

 

 

 

#include <iostream>

#define MAX 987654321

 

using namespace std;

 

int N;

int val[16][16];

int dp[16][1 << 16] = { 0 };

 

int func(int cur, int visited){

    if(dp[cur][visited] != 0)

        return dp[cur][visited];

        

    if(visited == (1 << N) - 1)

    {

        if(val[cur][0] != 0)

            return val[cur][0];

        else

            return MAX;

    }

    

    int result = MAX;

    for(int i = 0; i < N; i++)

    {

        if(!((1 << i) & visited) && (val[cur][i] != 0)){

            result = min(result, val[cur][i] + func(i, visited + (1 << i)));

        }

    }

    

    dp[cur][visited] = result;

    return result; 

}

 

int main() {

    cin >> N;

    for(int i = 0; i< N; i++){

        for(int j = 0; j < N; j++){

            cin >> val[i][j];

        }

    }

    

    cout << func(0, 1) << endl;

    return 0;

}