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 문제를 가져왔습니다.
TSP가 유명한 이유는 아직도 풀리지 않기 때문이에요 ㅜㅜ
문제가 원하는 답은 간단합니다.
"모든 정점을 한번씩만 거쳐 원래의 정점으로 돌아오는 최단경로(해밀턴 회로)"를 구하는 것이죠!
전체 문제에 대한 최단 경로를 찾았을 때 그 최단 경로의 부분 경로 또한 최단 경로라고 할 수 있기 때문에
DP가 성립합니다.
그럼 자세한 내용은 다음에 쓸게요!
'Algorithms > Baekjoon Algorithms' 카테고리의 다른 글
| 알고리즘 설계 - 동적계획법 (Dynamic Programming) (0) | 2019.06.26 |
|---|---|
| 백준 알고리즘 2655 - 가장 높은 탑 쌓기 (0) | 2019.06.26 |
| 백준 알고리즘 2156 문제 - 포도주 시식 (0) | 2019.06.24 |
| 백준 알고리즘 2193 문제 - 이친수 (0) | 2019.06.22 |
| 알고리즘 글을 쓰려고 합니다. (0) | 2019.06.22 |
