[백준][DP][Bitmasking] 2098번 외판원 순회

문제

1부터 N까지 마을이 있을 때 마을을 순회할 수 있는 최소비용을 구하시오.

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2098)

풀이

이 문제는 Bitmask를 사용해서 dp를 만들어 나가보려고 푼 문제입니다. 여기서는 모든 마을을 순회해야할 때 방문한 마을을 표시하기 위해 Bitmask를 사용해보았습니다. dp를 통해 문제를 풀기 위해 배열이 필요하고, Bitmask를 사용한다면 어느 마을을 방문했는지 알 수 있으므로 dp배열에서 바로 사용을 할 수 있게 됩니다. 1번 마을을 방문했다면 1이고, 2번 마을을 방문했다면 10, 3번 마을을 방문했다면 100, 세 마을을 전부 방문했다면 111로 표현할 수 있습니다. 이 때 특정한 i번째의 마을을 방문했는지 알려면 visited & 1<<i 한 값이 1이 나올 것입니다. 이러한 연산을 응용해서 0번에서 순회를 시작하고(순회하는 것이니 어느마을에서 시작하더라도 싸이클 경로로 돌아오게 됩니다.) 0번으로 돌아오는 탐색을 합니다. 재귀적으로 방문하지 않은 마을들을 탐색하며 수행하며 만약 dp에 해당 값이 존재할 때에는 해당 값을 그대로 사용하고, visitied의 모든 비트가 1이 될 때 모든 마을을 탐색한 것이므로(visitied == (1<<N)-1) 해당 마을에서 0번 마을로 돌아갈 수 있는지 판단한 후에 값을 반환합니다. 재귀적으로 수행하며 가장 작은 반환값을 dp에 배열에 저장해주게 되면 모든 함수가 종료했을 때의 return 값은 최소 비용값이 됩니다. dp배열이 없다면(메모리제이션을 해주지 않으면) N=16임에도 불구하고 바로 시간초과가 나게 됩니다! Bimask를 활용한다는 것이 어떻게 보면 쉬운데 어떠한 값에 활용을 해줄지 캐치하는 것도 중요한 것 같습니다.

코드 

https://github.com/kswim/Algorithm/blob/master/DP/2098.cpp