반응형
https://www.acmicpc.net/problem/2098
2098번: 외판원 순회
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j
www.acmicpc.net
[ 문제풀이 ]
https://rudalsd.tistory.com/36?category=1064608
[ 알고리즘 ] 외판원 순회 알고리즘(Traveling Salesperson Problem, TSP)
오늘 설명할 알고리즘은 외판원 순회 알고리즘(Traveling Salesperson Problem, TSP)입니다. 조합 최적화 문제로 전산학에서 연구된 가장 유명한 문제 중 하나입니다. 이 문제의 요구사항은 간단합니다.
rudalsd.tistory.com
위 글을 먼저 읽고 오시는 것을 추천드립니다!
이번 문제에서는 경로가 없는 경우도 존재하기 때문에 경로가 없는 경우 가지 않는다는 조건만 추가해주면 됩니다.
[ 소스 코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include<iostream> #include<cstring> using namespace std; int N; int arr[16][16]; int dp[16][(1<<16)]; int visitedAll; int dfs(int node, int via) { if (via == visitedAll) { if (arr[node][0] == 0) return 987654321; return arr[node][0]; } if (dp[node][via] != -1) return dp[node][via]; //방문한 적 있다면 dp[vode][via]출력 dp[node][via] = 987654321; //아닐경우 for (int i = 0; i < N; i++) { if (via & (1 << i)) continue; //이미 방문 if (arr[node][i] == 0) continue; //길이 없다면 dp[node][via] = min(dp[node][via], arr[node][i] + dfs(i, via | (1 << i))); } return dp[node][via]; } int main() { cin >> N; visitedAll = (1 << N) - 1; memset(dp, -1, sizeof(dp)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> arr[i][j]; } } int ans = dfs(0, 1); cout << ans; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 14939번 - 불 끄기 (C++) (0) | 2022.06.24 |
|---|---|
| [ 백준 ] 12850번 - 본대 산책2 (C++) (0) | 2022.06.23 |
| [ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++) (0) | 2022.06.21 |
| [ 백준 ] 9328번 - 열쇠 (C++) (0) | 2022.06.20 |
| [ 백준 ] 1167번 - 트리의 지름 (C++) (0) | 2022.06.19 |