백준 2098(2) (외판원 순회)

백준 2098 외판원 순회 (2)

문제 링크

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

들어가기에 앞서

저번 포스트를 참조해주세요!

traveling salesman problem을 완전탐색 알고리즘으로 해결하려면 O(n!)의 시간 복잡도가 걸린다는 사실을 알았습니다. 이를 개선하기 위해서 동적 계획법을 사용하자는 것이 아이디어입니다.

문제 접근

저번 포스팅에서, 동적 계획법을 사용하기 위한 상태(state)를 방문했던 도시와, 현재까지의 비용으로 정의했습니다.

상태 중 첫 번째, 방문했던 도시의 경우의 수는 꽤나 많습니다. 하지만 중요한 것은 방문했던 도시인 것이죠. 따라서, 방문했던 도시를 1, 방문하지 않았던 도시를 0으로 표현하는 bitmasking(비트마스킹) 기법을 사용합니다.

비트마스킹

비트마스킹

컴퓨터는 어떤 무엇인가를 나타낼 때, 0(off)/1(on)의 형태를 갖는 bit(2진수)로 나타냄을 알고 있습니다. 또한, bit를 이용한 연산은 어떤 연산들보다 빠르고 효율적입니다. 왜냐하면 제일 기초 연산이기 때문입니다. 따라서, 방문한 도시를 bit로 표현하자는 것입니다. 예를 들어서 5개의 도시 중, 1,2,3번 도시를 방문했다고 하면, 00111(2)=7(10)으로 나타내자는 것입니다.

현재 상태에서, 5번째 도시에 방문을 하는 경우는 아래와 같다고 생각할 수 있습니다.

now=now|1<<(5-1)  # |는 or 연산입니다.

이와 같이 and, or, not, xor등의 bit 연산을 상황에 맞게 적절히 이용하면, 다른 상황도 충분히 표현할 수 있어 보입니다. 이렇게, 어떤 상태를 bit와 bit연산을 사용해서 나타내는 기법을 비트마스킹이라고 합니다.

N<=16이하의 자연수이므로, 모든 상태를 나타내는데, 2^16-1=65535의 공간만 있다고 하면 충분히 나타낼 수 있어 보입니다.

그렇다면, 동적 계획법을 활용하기 위한 배열을

cache[나의 현재 도시][비트마스킹 기법을 사용한 도시의 방문여부] = 방문하지 않은 도시들을 방문한 후, 시작점으로 돌아오는 비용

위와 같이 선언한다면, (N)*(2^N)의 공간을 활용해서 해결할 수 있어 보입니다! 최소 한 번의 크기가 n인 반복문을 사용해야 할 것은 자명해 보입니다. 따라서, 최대한 컴퓨터의 cache를 사용하기 위해, [나의 현재 도시][비트마스킹] 형태로 선언하였습니다.

비트마스킹 기법을 사용하지 않는다면, 각 도시에 대해 [나의 현재 도시][1번 도시 방문 여부][2번 도시 방문 여부]….[n번 도시 방문 여부]로 n^(n+1)의 공간 복잡도를 사용합니다.

점화식

배열도 선언했으니, 점화식만 안다면 문제를 충분히 해결할 수 있어 보입니다. 점화식도 간단합니다.

ㅓㅕㅓ

위와 같이 점화식을 세울 수 있습니다.

dp[cur][visited] = a . 현재 도시 cur/ visited 상태일 때, visited에 속하지 않은 도시들을 방문하고, 처음 점으로 돌아오는 최소 비용

dp[cur][visited]=min(dp[cur][visited] , )

소스 코드

마무리하며