[백준 2098] 외판원 순회
알고리즘을 배우다보면 피할 수 없이 만나는 tsp문제이다. 이 문제의 입력인 N의 크기가 최대 16으로 극히 작은 문제이기 때문에 dp를 이용하여 문제를 풀 수 있다. 하지만 dp 사용에 있어서 tsp(currentCity, visited) 를 나타낼 때 visited를 배열(벡터)를 사용하기가 어려워진다. 메모이제이션을 해야하는데 visited 를 통째로 메모하기도 어렵고 공간 복잡도도 굉장할 것이다. 그래서 N이 작기때문에!!!!! 할 수 있는 방법으로 비트마스크를 사용한다. 0번째 도시를 이미 갔다. == 0번째 비트가 1 0번째 도시를 아직 안갔다. == 0번째 비트가 0 이런식으로 0번째부터 n-1번째 도시까지 총 n개의 도시를 비트로 체크할 수 있다. 여기서 메모이제이션을 위한 배열은 다음과 ..
