백준 10971 : 외판원 순회 2
https://www.acmicpc.net/problem/10971
1. 접근
- 가장 처음으로는 BFS 함수를 이용하여 구현해 보았다..그러나 시간 초과가 발생했다. 아무래도 직접 모든 노드를 돌아다니는 것이 많은 비효율을 가져온 것 같았다.
- 따라서, 굳이 돌아다니지 않고 경로를 미리 짜서 그 값만 확인하는 방식을 생각했다.
- 경로를 미리 짜기 위해서는, 모든 도시가 한번씩 나오면서 한 도시만 두번 나오는 경우를 구해야 했는데, 이전 문제에서 사용했던 순열과 그 의미가 같았다.
=> 순열을 이용하여 미리 경로를 짜고, 그때의 비용만 비교하자!
2. 나의 풀이
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> cities;
int map[11][11];
int n;
int mincost=0;
void TPS() {
int x, y;
int cost = 0;
for (int i = 0; i < cities.size()-1; i++) {
x = cities[i];
y = cities[i + 1];
if (map[x][y] == 0) return;
else cost += map[x][y];
}
if (map[cities[cities.size() - 1]][cities[0]] != 0) cost += map[cities[cities.size() - 1]][cities[0]];
else return;
mincost = min(mincost, cost);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
mincost += map[i][j]; //주의?
}
}
for (int i = 0; i < n; i++) {
cities.push_back(i);
}
do {
TPS();
} while (next_permutation(cities.begin(), cities.end()));
cout << mincost << "\n";
return 0;
}
Author And Source
이 문제에 관하여(백준 10971 : 외판원 순회 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jeongopo/백준-10971-외판원-순회-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)