반응형
풀이 ) DFS
TSP 문제이다.
도시의 수가 10개 이하이므로 DFS로 풀 수 있다.
방문 여부를 나타내는 visited 배열을 만들어서 각 도시를 방문했을 때, 방문하지 않았을 때 순서대로 재귀를 하고 모든 도시를 방문하고 마지막 도시에서 시작 도시로 돌아올 수 있으면 그 값을 기존의 결괏값과 비교해 최솟값을 구한다.
#include <cstdio>
#include <algorithm>
using namespace std;
int n, city[10][10], visited[10], ans = 1e9;
void dfs(int curr, int len, int tot);
int main(void)
{
scanf("%d", &n);
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
scanf("%d", city[i]+j);
dfs(0, 0, 0);
if(ans == 1e9)
printf("-1\n");
else
printf("%d\n", ans);
return 0;
}
void dfs(int curr, int len, int tot)
{
if(len == n-1){
if(city[curr][0])
ans = min(ans, tot+city[curr][0]);
}
else{
for(int i = 1; i < n; ++i)
if(city[curr][i] && !visited[i]){
visited[i]++;
dfs(i, len+1, tot+city[curr][i]);
visited[i]--;
}
}
}
반응형
'문제풀이 > 백준' 카테고리의 다른 글
[C++] 백준 - 11053 : 가장 긴 증가하는 부분 수열 (0) | 2020.03.25 |
---|---|
[C++] 백준 - 2644 : 촌수계산 (0) | 2020.03.24 |
[C++] 백준 - 2468 : 안전 영역 (0) | 2020.03.24 |
[C++] 백준 - 10451 : 순열 사이클 (0) | 2020.03.22 |
[C++] 백준 - 1157 : 단어 공부 (0) | 2020.03.22 |