[BOJ] 백준 17182. 우주 탐사선 (Gold II)

이 문제도 어떻게 보면 쉬운데, 어떻게 보면 어려운 문제.

스터디그룹 연습 D번으로 진행된 문제다.

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

17182번: 우주 탐사선

---

의식의 흐름 및 해설

이 문제를 보고 TSP가 떠올라 바로 TSP로 접근하려 했으나, 이미 방문한 행성을 다시 방문할 수 있다는 말에 다시 한 번 곰곰이 고민해보게 됐다.

이상하게 바로 아이디어가 떠오르지 않았으며, 꽤나 고생을 했는데,

 

생각해보니까 floyd 알고리즘이 어떤 행성을 방문하든 무조건 a->b까지의 최단거리를 구하는 알고리즘이었기 때문에 floyd 알고리즘 후 backtracking이나 tsp를 돌려주면 되는 문제였다.

 

floyd 알고리즘을 진행하면 그 사이에 행성을 중복 방문할 가능성을 염두에 두어야 한다. 다만, 이렇게 진행하면 무조건 a->b 간의 거리는 최단거리임이 보장이 되기 때문에 위와 같이 해결해주면 된다.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
const int MAX = 11;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
int N, K, a[MAX][MAX], ans = INF;
bool vis[MAX];
void solve(int cur, int cnt, int ret) {
	if (cnt >= N) {
		ans = min(ans, ret);
		return;
	}
	for (int i = 0; i < N; i++) {
		if (!vis[i]) {
			vis[i] = true;
			solve(i, cnt + 1, ret + a[cur][i]);
			vis[i] = false;
		}
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> a[i][j];
		}
	}
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				a[i][j] = min(a[i][k] + a[k][j], a[i][j]);
			}
		}
	}
	vis[K] = true;
	solve(K, 1, 0);
	cout << ans;
}

---

어떻게 보면 되게 쉬운데,

중복 방문을 허용한다는 말 때문에 돌아돌아 생각해버린 문제.

이렇게 또 좋은 경험을 쌓아간다.

 

개인적으론 G3정도라 생각한다.