728x90
반응형
이 문제는 brute force문제이다.
한 도시를 출발하여 n개의 도시를 다 거치고 원래 도시로 돌아오는 방법 중 최소 비용을 출력하는 문제이다.
시작점과 동일한 도시이고 n개의 도시를 순회했을 경우 최소비용을 구하도록 했다.
if(start == y && target == n){
if(sum < minSum){
minSum = sum;
}
return;
}
그리고 y에서 시작했을 때 도시를 순회하기 위한 비용이 최소 비용을 넘지 않을 경우 계속해서 순회를 하도록 했다.
for(int i = 0; i < n; i++){
if(visited[y] == 1 || path[y][i] == 0) continue;
if(sum < minSum){
visited[y] = 1;
dfs(start, target + 1, i, sum + path[y][i]);
visited[y] = 0;
}
}
모든 도시를 시작점으로 해서 순회하는 비용 중 최소 비용을 구했다.
for(int i = 0; i < n; i++){
dfs(i, 0, i, 0);
}
따라서 전체적인 코드는 이렇다.
//외판원 순회 2
#include <iostream>
using namespace std;
int visited[11];
int path[11][11];
int n, minSum = 987654321;
void dfs(int start, int target, int y, int sum){
if(start == y && target == n){
if(sum < minSum){
minSum = sum;
}
return;
}
for(int i = 0; i < n; i++){
if(visited[y] == 1 || path[y][i] == 0) continue;
if(sum < minSum){
visited[y] = 1;
dfs(start, target + 1, i, sum + path[y][i]);
visited[y] = 0;
}
}
}
int main(void){
cin >> n;
fill_n(visited,11,0);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> path[i][j];
}
}
for(int i = 0; i < n; i++){
dfs(i, 0, i, 0);
}
cout << minSum;
}
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 부분 수열의 합 2 (0) | 2020.11.10 |
---|---|
[algorithm] 백준 - 카잉 달력 (0) | 2020.11.10 |
[algorithm] 백준 - 숨바꼭질 4 (0) | 2020.11.05 |
[algorithm] 백준 - 숨바꼭질 6 (0) | 2020.11.04 |
[algorithm] 백준 - 조합 0의 개수 (0) | 2020.11.04 |