백준 - 우주 탐사선 (17182)

1. 문제 링크

우주 탐사선

2. 풀이

플로이드 와샬 + 외판원 순회로 풀었습니다.

1. 플로이드 와샬로 각 행성 사이의 최소 거리를 계산

int d[10][10];

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

for (int k = 0; k < n; k++)
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

d[a][b]는 a행성에서 b행성으로 가는 최소 거리가 저장됩니다.

2. 외판원 순회로 정답 계산

const int INF = 0x3f3f3f3f;
int n, k;
int d[10][10], dp[10][1 << 10];

int solve(int p, int visited) {
	// 모든 행성을 방문했을 때
	if (visited == (1 << n) - 1) return 0;

	int &ret = dp[p][visited];

	if (ret != -1) return ret;

	ret = INF;

	for (int i = 0; i < n; i++) {
		// 방문한 행성일 때
		if ((visited & (1 << i)) != 0) continue;

		ret = min(ret, d[p][i] + solve(i, visited | (1 << i)));
	}

	return ret;
}

p는 현재 방문하고 있는 행성,
visited는 지금까지 방문한 행성이 비트마스크로 표현돼 있습니다.

이 때 이미 방문한 행성은 넘어갑니다.
1번 플로이드 와샬 부분에서
각 행성 사이의 거리가 최소 거리로 계산된 엣지로 재구성된 그래프,
즉, 새로운 그래프를 탐색한다고 생각하시면 됩니다.

무슨 말이냐면,
p -> i로 가는 최소 경로가 p -> a -> b -> i라고 가정할 때,
p -> a -> b -> i의 값을 p -> i 값으로 하는 새로운 그래프라는 의미입니다.
이로서 사실 중복하게 행성을 방문하고 있지만, 코드상에서 신경쓰지 않아도 됩니다.

3. 전체 코드

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
int n, k;
int d[10][10], dp[10][1 << 10];

int solve(int p, int visited) {
	// 모든 행성을 방문했을 때
	if (visited == (1 << n) - 1) return 0;

	int &ret = dp[p][visited];

	if (ret != -1) return ret;

	ret = INF;

	for (int i = 0; i < n; i++) {
		// 방문한 행성일 때
		if ((visited & (1 << i)) != 0) continue;

		ret = min(ret, d[p][i] + solve(i, visited | (1 << i)));
	}

	return ret;
}

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

	cin >> n >> k;

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

	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

	memset(dp, -1, sizeof(dp));
	cout << solve(k, 1 << k);

	return 0;
}