문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 풀이 외판원 문제는 유명한 알고리즘 문제이다. TSP라고 하는데, 해당 문제를 풀기 위해서 DP나 Branch & Bound 알고리즘이 사용된다. 처음에는 임의의 출발점에 대해서 모든 최단거리를 구하려고 했지만, 규칙을 발견했다. 1->2->3->4->5->1와 2->3->4->5->1->2의 값이 같다는 사실이다. 이유는 항상 마지막 지점에서 출발..
문제 목표 n개의 도시로 판매 출장을 계획하고 있는 외판원이 각 도시를 한 번씩 방문하고, 다시 출발한 도시로 돌아오는 가장 짧은 여행길을 찾는 것. --> 최단 경로 문제 --> 출발한 도시로 다시 돌아오는 부분에서 해밀턴 회로와 동일한 개념. 이 문제는 weighted, directed graph이다. 각 도시에서 도시로 가는 비용이 있고, 방향이 정해져 있다.(여기서 비용은 음이 아닌 정수로 가정한다) 만약 v1을 출발점으로 잡는다면 가능한 경로와 그에 비용은 아래와 같다. [v1->v2->v3->v4->v1] = 22 [v1->v3->v2->v4->v1] = 26 [v1->v3->v4->v2->v1] = 21 v1에서 출발할때의 최적의 경로는 [v1->v3->v4->v2->v1]이고 그 비용은 2..
