백준 2098 - 외판원 순회

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

2098번: 외판원 순회

썸네일은 긴팔원숭이입니다. 문제 이름보고 생각나서.. 해봤어요..

 

정답과 비슷하게 접근하는데 까지는 성공했지만,, 사소한 디테일을 잘 처리하지 못해 다른 풀이를 참고하여 풀었다.

다만 비트마스킹을 활용하여 푸는 대표적인 DP 문제이므로 정석 풀이를 참조해 글을 작성한다.

 

비트마스킹 기본

'현재 상태'를 배열이 아닌 0101의 비트로 처리한다. 예를 들어 4개의 도시에 대해, 현재 상태가 5 = 0101(2)일 경우 1,3번 도시를 방문했다고 보면 된다. 비트마스킹은 작은 크기의 입력에 대해 배열보다 빠르고 간단(사실 나한텐 안 간단함)한 처리를 가능케 한다.

 

비트마스킹은 비트 연산자를 통해 구현한다.

<< 연산자 : i번 원소를 선택

 - ex) 1 << (5 - 1) = 10000(2) ==> 5번 도시

 

& 연산자 : 원소의 포함 여부를 확인

 - ex) 0101(2) & 0001(2) > 0이므로 1번 도시 포함

 

| 연산자 : 원소를 현재 상태에 추가

 - ex) 0001(2) | 0100(2) = 0101(2)로 현재 상태에 3번 도시 추가

 

^ 연산자 : 원소의 포함 여부를 반전

 - ex) 0101(2)에는 1번 도시가 있으나 0101(2) ^ 0001(2) = 0100(2)를 통해 1번 도시 제거

DP

문제의 핵심인 DP 풀이를 알아보자.

 

DP식 정의

dp[i][j] := j번 도시를 마지막으로 하여 비트마스크 i의 도시들을 방문하는 최소 비용

문제에서 요구되는 값은 dp[11....111][0]이다.

 

초깃값

dp[1 << i][i] = cost[0][i]

맨 처음 0번 도시에서 출발하여 i번 도시 하나만 방문하는 방법은 한 가지 뿐이므로, 초깃값 정의가 가능하다.

0이 아닌 도시에서 출발하는 최적의 순회 경로가 존재한다면, 그 경로를 타고 돌아 0번 도시에서 출발해도 똑같은 결과를 얻는다. 아래 그림을 참고하자.

출처 : https://www.acmicpc.net/board/view/29929

0번 도시에서 출발했기 때문에, 한바퀴 돌아 0번으로 돌아오는 dp[11....111][0]가 정답이 된다.

 

점화식

N개의 도시를 순서대로 방문하는 방법은 N! 개 존재하지만, 순서를 제거하면 경우의 수가 2^N개로 크게 줄어든다.

이제 이 모든 경우를 일일히 확인하면서, 현재 상태 S에 포함된 모든 도시 i에 대해 'i번 도시를 마지막으로 하여 현재 상태 S에 도달하는 최소 비용'을 찾는다. dp식 정의에 따르면 이 값은 dp[S][i]이다.

 

실제 점화식은 다음과 같다.

 - S에 속한 다른 원소 j (i <> j)에 대하여, dp[S][i] =  dp[S - i][j] + cost[j][i]

S - i는 기존 상태에서 i를 제거한 상태이며, 코드 상으로는 비트 연산자를 이용해 표현한다.

 

예를 들어 S = 1101(2)라고 하자.

dp[S][1] : S - i = 1100(2)이므로 j가 될 수 있는 원소는 3, 4이다.

따라서 dp[S][1]는 j가 3, 4일 때 dp[1100(2)][3] + cost[3][1], dp[1100(2)][4] + cost[4][1] 중 더 작은 값이다.

 

더 쉽게 풀어 설명하면 3, 4번 도시를 거쳐 1번 도시를 방문하는 경우는 3 - 4 - 1, 4 - 3 - 1 두 가지이므로 둘 중 더 작은 값을 선택하면 된다.

 

유효하지 않은 경로, 즉 dp[S - i][j] 또는 cost[j][i]가 존재하지 않는 경우에는 생략한다.

 

코드 보기

//초깃값
for (int i = 0; i < N; i++) {
    if(cost[0][i])
        dp[1 << i][i] = cost[0][i];
}

for (int field = 1; field < (1 << N); field++) {
	//j 선택
    for (int u = 0; u < N; u++) {
        if ((field & (1 << u)) == 0) continue;
		//i 선택
        for (int v = 0; v < N; v++) {
            if ((field & (1 << v)) == 0) continue;
            
            int a, b;
            
            //유효하지 않은 경로
            if ((a = dp[field ^ (1 << v)][u]) < 0) continue;
            if ((b = cost[u][v]) == 0) continue;
            
            //dp[S][i]
            int& c = dp[field][v];

			//모든 경우 확인하며 최솟값 갱신
            c = (c < 0 ? a + b : min(c, a + b));
        }
    }
}

//목푯값
cout << dp[(1 << N) - 1][0] << endl;

 

사실 풀이를 쓰면서도 알듯말듯하다. 표준 문제라고하니, 혼자 고민하지 말고 다른 사람들의 세련된 풀이(내꺼 말고)를 보고 머리에 심어두자.