[백준/C++] 17182. 우주 탐사선

문제

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

17182번: 우주 탐사선

요약 : 

모든 행성을 탐사하는데 걸리는 최소 시간을 계산하여라.

탐사 후 다시 시작 행성으로 돌아올 필요는 없으며 이미 방문한 행성도 중복해서 갈 수 있다.

풀이

DFS로 정해진 시작점으로부터 모든 행성을 방문하는데 드는 최소 시간을 구해야 하는데, 그 전에 

입력된 간선들을 이용해서 모든 노드 - 모든 노드 간의 최소 거리의 2차원 배열을 구해놓고 시작해야 한다. 

최소 거리 2차원 배열을 채우는 데에는 플로이드 와샬 알고리즘을 이용하였다.

 

플로이드 와샬이 O(V^3) 복잡도를 가지는데, 이 문제에서 V 최대 개수가 10이기 때문에 부담없이 사용할 수 있었다. 

코드

#include <cstdio>
#include <algorithm>

#define sc scanf_s 
#define MAX 987654321

using namespace std;

int N, K;
int dist[10][10]; // maxN: 10
bool visited[10];

int result = MAX;
void DFS(int start, int d, int visitCount) {
	if (result < d) return;
	if (visitCount == N) {
		result = min(result, d); return;
	}
	for (int i = 0;i < N;i++) {
		if (visited[i]) continue;
		visited[i] = 1;
		DFS(i, d + dist[start][i], visitCount + 1);
		visited[i] = 0;
	}
}
int main() {
	sc("%d %d", &N, &K);
	for (int i = 0;i < N;i++) 
		for (int j = 0;j < N;j++) 
			sc("%d", &dist[i][j]);

	// 플로이드 와샬 
	for (int k = 0;k < N;k++) {
		for (int i = 0;i < N;i++) {
			for (int j = 0;j < N;j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	// 모든 행성을 탐사하는데 걸리는 최소 시간 찾기 
	visited[K] = 1;
	DFS(K, 0, 1);
	printf("%d\n", result);
	return 0;
}

 

결과