[알고리즘] #11. DP(DynamicPrograming): 비트마스킹(외판원 순회)

#비트마스킹(Bit Masking)

알고리즘보다는 bit단위 테크닉에 가까운 기법

+ 정수를 이진수로 표현하는것을 활용 =>  bit단위로 값을 보존하며 진행

+ 0=flase=off / 1=true=on   => 비트로 상태를 나타낼수 있다.

+ 최적의 성능을 얻는데 필수적인 기법(컴퓨터 하드웨어)

 

 

#비트의 활용

집합 A={0, 1, 2, 3, 4}

A의 부분집합을 표현하는 방법

1. int형 인덱스 활용

int[] arr_1234 = {1, 1, 1, 1, 0}

int[] arr_124 = {1, 0, 1, 1, 0}

   => 문제점: 메모리낭비, 오버헤드 증가

2. 비트마스킹 활용 => 1개의 정수로 표현가능

{1, 2, 3, 4} = 11110 => 30

{1, 2, 4} = 10110 => 22

 

#비트연산

 

1. AND 연산(&)

대응하는 두 비트가 모두 1일 때, 1을 반환.

1010 & 1111 = 1010

 

2. OR 연산(|)

대응하는 두 비트가 모두 1 또는 하나라도 1일 때, 1을 반환.

1010 | 1111 = 1111

 

3. XOR 연산(^)

대응하는 두 비트가 서로 다르면 1을 반환.

1010 | 1111 = 0101

 

4. NOT 연산(~)

비트의 값을 반전하여 반환.

~1010 = 0101

 

5. 시프트(Shift) 연산(>>, <<)

왼쪽 또는 오른쪽으로 비트를 옮긴다.

00001010 << 2 = 101000
00001010 >> 2 = 000010 

                                                                       출처: https://mygumi.tistory.com/361 [마이구미의 HelloWorld]

 

i번 비트값 확인

result = now & (1<<i)

: i번째 비트만 1인 값과 현재값의 AND연산 => i번째 값을 확인가능

 

i번 비트값을 1로 변환

now |= (1<<i)

: i번째 비트만 1인 값과 현재값의 OR연산 => i번째 값이 1로 변환됨

 

i번 비트값을 0으로 변환

now &= ~(1<<i)

: i번째 비트만 0인값과 현재값의 AND연산

 

 

 

#외판원순회

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

2098번: 외판원 순회

#dp[current][visited]: 현재 visited를 방문한후 current에 있을때 방문하지 않은 나머지 마을을 방문한후 출발점으로 되돌아올때의 최소 비용.

#비트를 이용하여 방문 도시들을 표현: int는 4바이트 즉 32비트이므로 1개의 변수로 최대 32개의 도시의 방문여부를 표현가능하다.

#기저사례: visited = (1<<N)-1

#점화식: tsp(current, visited) = min( tsp(next, visited+next) + w[current][next] )

#include <iostream>
#define IMPOSSIBLE 100000000

using namespace std;

int w[17][17];
int N;
int dp[17][1<<16];

int tsp(int current, int visited) {
    //dp가 이미 구해져있는 상태라면 dp값을 리턴
    if (dp[current][visited] != 0)
        return dp[current][visited];
    //기저사례: 모든 도시들을 방문했을때 => 현재도시에서 시작도시까지의 비용을 리턴
    if (visited == (1<<N)-1) {
        if (w[current][0] != 0)
            return w[current][0];
        return IMPOSSIBLE;
    }
    dp[current][visited] = IMPOSSIBLE;
    //모든도시를 거쳐갈때의 비용을 비교하여 최적값을 저장
    for (int i=0; i<N; ++i) {
        //방문한 도시거나, 길이없는경우
        if (visited & (1<<i) || (w[current][i]==0))
            continue;
        //현재값과 해당 도시를 방문했을때의 값을 비교
        dp[current][visited] = min(dp[current][visited], tsp(i, (visited | (1<<i))) + w[current][i]);
    }
    return dp[current][visited];
}
int main() {
    cin >> N;
    for (int i=0; i<N; ++i) {
        for (int j=0; j<N; ++j) {
            cin >> w[i][j];
        }
    }
    cout << tsp(0, 1) << '\n';
}

참고: https://hsp1116.tistory.com/40