Study hard
(c++)백준 10971번: 외판원 순회 2 본문
https://www.acmicpc.net/problem/10971
[풀이]
가능한 모든 경로에 대한 비용들을 비교하여 최솟값을 구하였다.
방문하는 도시의 순서에 따라 최종 비용이 달라지므로 순열을 사용하였다.
마지막으로 방문하는 도시에서 출발한 도시로 갈 수 있는지 확인해줘야 한다.
모든 도시가 출발지점이 될 수 있다.
#include <iostream>
#include <algorithm>//min
using namespace std;
int N;
int Min = 99999999;
int startCity;
int Cost[11][11];
bool visited[11];
//순열 구하기->모든 경우의 경로에 대한 비용 비교
void getCost(int cnt, int curCity, int cost) {
if (cnt == N) {
if (Cost[curCity][startCity] != 0) {
Min = min(Min, cost + Cost[curCity][startCity]);
return;
}
}
for (int i = 0; i < N; i++) {
if (Cost[curCity][i] != 0 && visited[i] == false) {
visited[i] = true;
getCost(cnt + 1, i, cost + Cost[curCity][i]);
visited[i] = false;
}
}
}
void solution() {
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> Cost[i][j];
}
}
//모든 도시가 출발점이 될 수 있음
for (int i = 0; i < N; i++) {
startCity = i;
visited[i] = true;
getCost(1, i, 0);
visited[i] = false;
}
cout << Min << endl;
}
int main() {
solution();
return 0;
}
'백준 > 완전 탐색' 카테고리의 다른 글
(c++)백준 10819번: 차이를 최대로 (0) | 2020.07.13 |
---|---|
(c++)백준 1451번: 직사각형으로 나누기 (0) | 2020.07.11 |
(c++)백준 1107번: 리모컨 (0) | 2020.07.04 |
(c++)백준 1476번: 날짜 계산 (0) | 2020.07.04 |