c언어 17182번 우주 탐사선 (백준)

#include <stdio.h>
int n, key;
int v[10] = {0}; //백트래킹용 방문했는지 안했는지
int d[10][10] = {}; //최단 거리 배열
int ans = 100000000; //정답을 담는 변수

void loop(int s, int cnt, int sum) { //백트래킹
	if(cnt == n-1) {
		if(ans > sum) ans=sum;
		return;
	}
	
	for(int i=0; i<n; i++) {
		if(v[i]) continue;
		sum+=d[s][i];
		v[i]=1;
		loop(i, cnt+1, sum);
		v[i]=0;
		sum-=d[s][i];
	} return;
}

int main(void) {
	int INF = 100000000; //input
	scanf("%d %d", &n, &key);
	for(int i = 0; i<n; i++) 
	for(int j = 0; j<n; j++) scanf("%d", &d[i][j]);
	
	for(int k=0; k<n;k++) //floyd warshall
	for(int i=0; i<n; i++)
	for(int j=0; j<n; j++) {
		if(d[i][k] + d[k][j] < d[i][j])
		d[i][j] = d[i][k]+d[k][j];
	}
	//백트래킹으로 최단거리 찾기
	v[key] = 1; 
	loop(key, 0, 0);
	printf("%d", ans); //정답 출력
}

풀이 : Floyd Warshall -> 백트래킹

0. 행성의 개수, 출발 행성, 기본 행성간 거리 입력받음

1. floyd warshall

2. 백트래킹

3. 결과 출력