✓

태그:

32. 동적 계획법 3 CLASS 5 ESSENTIAL

무엇을 저장해야 (그나마) 효율적인 DP가 될까요…??

풀이 비스무리한거 보기

유명한 외판원 순회 문제(TSP, Travelling Salesman Problem)의 작은 버전 입니다. 도시의 수가 최대 16개밖에 되지 않아 모든 경우를 탐색할 수 있을 것 같습니다. 물론 $n!$번의 연산을 하겠다는 것이 아니라 DP를 사용해서 최대 $n\times 2^n$번의 연산을 하겠다는 것입니다.($n!$이랑 $n\times 2^n$이랑 비교하면 놀라운 수준의 차이입니다!¹) 그렇다면 DP 배열에 무엇을 저장해야할까요? 바로 현재 위치한 도시와 지금까지 방문한 도시입니다. 남은 도시를 가장 적은 비용으로 이동하는 경우만 필요하기 때문입니다.

그런데 지금까지 방문한 도시를 또 배열로 저장하려니 메모리와 알고리즘 구상의 측면에서 상당히 비효율적입니다. 여기서 사용할 것이 비트필드입니다. 16개 도시면 16비트짜리 정수 하나로 방문 여부를 체크할 수 있습니다. 이것을 DP 배열의 하나의 인덱스로 하고 하나의 인덱스를 현재 위치한 도시로 두어 2차원 배열을 구성할 수 있겠습니다. 즉, 16개의 도시가 주어졌을 때 아래와 같은 구조가 됩니다.

int dp[16][1 << 16];
/*
dp[i][j]: 현재 i번째 도시에 위치하며
현재까지 방문한 도시의 정보가 j에 저장됨.
지금까지 방문한 도시 k에 대해서 j & (1 << k) != 0을 만족함.
*/

이제 DP 배열을 기반으로 도시를 순회하면 최소의 비용을 구할 수 있습니다.

---

1. n이 충분히 작을 때에는 $n!$이 더 작아보일 수도 있겠으나, n=6부터 $n\times 2^n$이 더 작습니다.

   n	$n!$	$n\times 2^n$
   1	1	2
   2	2	8
   10	3628800	10240
   16	20922789888000	1048576
   100	9.33×10157	1.26×1032
   106	8.27×105565708	9.90×10301035

   ↩

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-03-09 22:06:38

---