Jonyo Programming

[BOJ 2098(G1)리뷰] 컴퓨터 분야에서 TSP 라고 불리는 굉장히 유명한 문제라고 한다. 한 도시에서 출발하여 N개의 도시를 모두 방문하였을 때 최소비용을 구해야 한다. 처음에 그냥 간단한 최소 스패닝 트리를 구성하는 문제거나, 최단거리를 구하는 문제인 줄 알았는데 모든 도시를 방문해야 하며(방문이 가능할 경우) 다시 도착점으로 돌아와야 한다는 등의 조건때문에 결국 완전탐색을 해야 한다. 하지만 이 문제의 N의 최대값은 16이므로 완전탐색으로 구현하게 되면 16!이라는 어마어마한 시간복잡도를 가지게 된다. 따라서 다이나믹 프로그래밍을 이용하여 시간효율을 증가시켜야 한다. 그리고 이 때, DP를 효율적으로 사용하기 위하여 비트마스킹 이라는 개념을 사용한다. 나도 이 문제에서 처음사용해봤는데 굉장히 ..