Inflearn Community Q&A

안녕하세요 선생님 🙂

외판원 순회 문제 질문있습니다.

dp를 비트플래그를 이용해서 방문여부를 체크한다는 아이디어가 정말 참신하게 다가오는 것 같습니다.

이 문제를 처음 접했을 때, 비트플래그가 아닌

dp[MAX_N][MAX_N * MAX_N] 형태를 생각했었는데요, 이 방식으로 푼다면 배열의 범위가 dp[16][65536]이 아닌 dp[16][256]이 됩니다. 이게 시간복잡도와 공간복잡도 면에서 더 효율적이라고 생각이 들지만, 방문처리를 어떻게 해야할지 모르겠더라구요. 혹시 이렇게도 풀 수 있는 방법이 있을까요?