외판원 순회 문제 (Traveling Salesman Problem)

분명 1학년때 배웠지만... 기억이 나지 않기에 관련문제를 풀며 알아보자.

 

외판원 순회 문제

N 개의 도시가 있고, 도시와 도시를 연결하는 길이 있다. 길은 가중치를 갖는다. 임의의 한 도시에서 출발하여 N개의 도시를 모두 방문하고 원래의 도시로 돌아오고자 한다. 한번 방문한 도시를 다시 방문할 수 없다(시작한 도시 제외). 경로의 가중치들의 합이 최소가 되는 순환경로를 찾는다.

 

즉, 전부 방문할 때 가장 적은 비용이 드는 경로를 찾는것이다.

 

관련 문제를 보며 확인해보자

https://www.acmicpc.net/problem/24512

24512번: Bottleneck Travelling Salesman Problem (Small)

 난이도 Silver 2의 비교적 쉬운 문제이다.

구하고자 하는 것은 정점 간 이동 비용의 최댓값을 최소화하는 것이다.

 

일단 모든 경우의 일주에 대해 알아봐야하기에 나는 재귀를 사용했다.

문제에서 정점의 개수 N은 최대 9이기에 N*N의 리스트 cost를 만들어 cost[from][to]=value 와 같이 나타내었다.

재귀로 permutation을 나타낼때의 코드와 비슷하게 작성했다.한번 전부 방문했다면 그 사이의 cost의 최대값을 찾고 그러한 최대값들의 최소가 되는 경로를 찾았다.

 

https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

난이도 Gold 1의 문제이다.

포인트는 비트마스킹을 이용하는 것이다.