우선 처음 문제를 읽고나서 든 생각은, 어떻게 visited 체크를 하느냐 였습니다. 또한 dp를 사용하지 않으면 O(N!)의 시간복잡도를 갖기 때문에 dp를 통해 문제를 해결해 나가야한다는 것을 인지하고 있었습니다. visited체크를 tsp 로직 함수마다 풀어줘 버리면 체크하는 의미가 없기 때문에 풀어주지 않겠다는 생각이 들었습니다. 그러므로 재귀적으로 특정 조건들에 의해서 다음 노드로 들어간 후에 그 노드에서 갈 수 있는 가장 짧은 길을 dp 배열에 넣으면 되겠다는 생각이 들었습니다. 하지만 여전히 visited를 어떻게 설정해야 할지 감이 오지 않았습니다.
visited 체크 기법을 스스로 터득했으면 좋았겠지만, 아이디어가 도저히 생각이 나지 않아서 구글링을 했습니다. 비트마스크로 visited 체크를 할 수 있다는 것을 알게 되었습니다. 일단 그 사실을 알고 나서 문제에 접근했습니다. 메모리 측면에서는 N이 16까지 이기 때문에 2의 16승인 65536이므로 int의 크기인 4를 곱해도 여유롭다는 생각이 들었습니다. 또한 비트마스크로 visited를 표현을 하면 굉장히 편리하겠다는 생각을 했습니다.
dp[N][visited] = std::min(dp[N][visited], tsp(next, next + visit) + W[cur][next]);
위 점화식을 보고나서는 visited 체크배열을 따로 두는 것이 아닌 비트 연산을 통해 dp 배열 인덱스로 들어간다는 사실을 알게되었습니다. 위 visited 파트에서 계산한 메모리에 N인 16을 곱해도 (16 * 65536 * 4 ) 메모리는 여유롭기 때문에 해당 점화식을 어떻게 코드로 녹여내느냐가 관건이었습니다.
위의 점화식을 보고나서 @suhshin과 함께 토론해 가며 문제를 풀었습니다.