[C++]백준 17182번 : 우주탐사선

https://www.acmicpc.net/problem/17182

17182번: 우주 탐사선

 

1. 접근

K행성에서 모든 행성을 방문하는 최단비용을 계산해야하므로 플로이드-와샬 알고리즘을 통해 모든 행성 간의 최단거리를 구한 후, dfs로 전체방문 최소비용을 구한다.

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

using namespace std;

int N, K;
int w[10][10];
int chk[10], ans = INT_MAX;

void dfs(int idx, int cnt, int cost){
	if (cnt == N - 1){
		ans = cost;
		return;
	}

	for (int i = 0; i < N; i++){
		if (!chk[i] && ans > cost + w[idx][i]){
			chk[i] = true;
			dfs(i, cnt + 1, cost + w[idx][i]);
			chk[i] = false;
		}
	}
}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> K;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			cin >> w[i][j];
		}
	}

	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			for (int k = 0; k < N; k++){
				w[j][k] = min(w[j][k], w[j][i] + w[i][k]);
			}
		}
	}

	chk[K] = true;
	dfs(K, 0, 0);

	cout << ans;

	return 0;
}

 

2. 플로이드-와샬 알고리즘

모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘

 

=> cost[i][j] = min( cost[i][j], cost[i][k] + cost[k][j] )

 

3중 for문으로 모든 정점 간의 경로의 비용에 대해 모든 정점을 중간 경로로 거쳤을 때의 비용과 비교해주는 것으로 구현 가능하다.