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

문제 링크

17182번: 우주 탐사선

문제 요약

우주 탐사선 ana호가 행성을 탐사한다. 행성들 사이의 거리가 주어질 때, k번 행성에서 출발해 모든 행성을 탐사하기 위한 최소 이동 거리를 구해야 한다.

접근 방법

모든 정점을 방문하는 최소 비용을 구하는 것이기 때문에, 비트마스킹으로 풀기 좋은 문제입니다.

풀이는 간단합니다. 모든 정점 사이의 최단경로의 길이를 미리 구해줍니다. 모든 정점 쌍 사이에 대해 구하는 것이기 때문에, 플로이드-와샬 알고리즘을 쓰는 쪽이 효율적입니다. 그리고 k번부터 출발해서 모든 정점을 방문하는 모든 경우의 수를 시도해 최솟값을 출력하면 됩니다. N이 10 정도이기 때문에 시간초과는 나기 힘듭니다.

비트마스킹을 써도 되고, 아니면 그냥 bool 배열을 이용해서 재방문을 체크해줘도 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 11, INF = 1e9;
int n, k, dist[MAX][MAX], ans = INF;

void func(int now, int cnt, int bit, int sum) {
	if (cnt == n) {
		ans = min(ans, sum);
		return;
	}

	for (int i = 0; i < n; i++) {
		if (bit & (1 << i))
			continue;

		func(i, cnt + 1, bit | (1 << i), sum + dist[now][i]);
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			dist[i][j] = INF;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> dist[i][j];

	for (int i = 0; i < n; i++)
		for (int k = 0; k < n; k++)
			for (int j = 0; j < n; j++)
				if (dist[i][k] != INF && dist[k][j] != INF)
					dist[i][j] = min(dist[i][j],  dist[i][k] + dist[k][j]);

	func(k, 1, 1 << k, 0);

	cout << ans << '\n';
	return 0;
}