6012 : 백트래킹 — 외판원 문제
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
외판원 문제(Traveling Salesperson Problem, TSP)는 $N$개의 도시와 도시들 사이의 이동 비용이 주어졌을 때, 임의의 도시에서 출발하여 모든 도시를 정확히 한 번씩만 방문하고 다시 원래의 출발 도시로 돌아오는 최소 비용의 이동 경로를 찾는 문제입니다.
백트래킹 DFS를 기반으로 구현하되, 현재까지 누적된 비용이 이미 발견한 전체 최소 비용 이상이 되는 순간 탐색을 즉시 종료하는 가지치기(Pruning) 기법을 반드시 적용하십시오.
[제약 조건]
• 도시 수 $N$: $2 \le N \le 10$ (정수)
• 이동 비용: $0 \le w_{ij} \le 10^6$ (정수, 0이면 이동 불가)
백트래킹 DFS를 기반으로 구현하되, 현재까지 누적된 비용이 이미 발견한 전체 최소 비용 이상이 되는 순간 탐색을 즉시 종료하는 가지치기(Pruning) 기법을 반드시 적용하십시오.
[제약 조건]
• 도시 수 $N$: $2 \le N \le 10$ (정수)
• 이동 비용: $0 \le w_{ij} \le 10^6$ (정수, 0이면 이동 불가)
입력 설명
첫째 줄에 도시의 수 $N$이 주어집니다. ($2 \le N \le 12$)
둘째 줄부터 $N$개의 줄에 걸쳐 각 도시 사이의 이동 비용을 나타내는 $N \times N$ 인접 행렬이 공백으로 구분되어 주어집니다.
행렬의 $W[i][j]$는 도시 $i$에서 도시 $j$로 가기 위한 비용입니다. 비용은 $100$ 이하의 자연수이며, 갈 수 없는 경우에는 $0$으로 주어집니다.
둘째 줄부터 $N$개의 줄에 걸쳐 각 도시 사이의 이동 비용을 나타내는 $N \times N$ 인접 행렬이 공백으로 구분되어 주어집니다.
행렬의 $W[i][j]$는 도시 $i$에서 도시 $j$로 가기 위한 비용입니다. 비용은 $100$ 이하의 자연수이며, 갈 수 없는 경우에는 $0$으로 주어집니다.
출력 설명
모든 도시를 한 번씩 거쳐 출발지로 돌아오는 최적 순회의 최소 비용을 출력합니다.
만약 그러한 순회 경로가 존재하지 않는 경우에는
만약 그러한 순회 경로가 존재하지 않는 경우에는
-1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
35도움
시작 도시는 어느 도시로 잡든 항상 사이클의 비용 합이 동일하므로, 항상 0번 도시에서 시작하여 0번 도시로 돌아오는 경로로 고정하여 탐색합니다.
cost >= min_cost 조건으로 가지치기를 강력하게 적용합니다.