[백준17182] 우주 탐사선 (C++)

📌 문제

BOJ 바로가기

모든 행성을 탐색할 수 있는 최소 시간을 구하는 문제이다.

🗡 풀이

📍 가중치가 같지 않고, 모든 위치에서의 최단경로를 구해야 하기 때문에 플로이드-워셜 알고리즘을 이용하였다.

📍 DFS와 백트래킹을 이용해 문제를 해결했다.
go(int idx, int planet, int sum 함수를 만들었다. idx는 방문한 행성의 개수, planet은 현재 방문한 행성의 번호, sum은 지금까지 걸린 시간을 의미한다. idx == n 이 되는 순간까지 재귀함수를 돌려준 후, ans에 sum의 최솟값을 담아주면 된다.

📍 "이미 방문한 행성도 중복해서 갈 수 있다."라는 문구 때문에 문제를 푸는 데 오래 걸렸다. 알고 보니 신경쓸 필요 없는 문구였다.. 이것 때문에 한참 잡고 있다가 결국 구글링을 한 결과 간선에는 음수가 없기 때문에 어차피 최단경로는 중복방문하지 않은 경로가 된다고 한다..!!

🚩 소스코드

#include <iostream>
#include <algorithm>
using namespace std;
#define INF 987654321;

int n, ans = 2147483647, t[10][10];
bool visited[10] = { false };

void go(int idx, int planet, int sum) {
	if (idx == n) {
		ans = min(ans, sum);
		return;
	}
	for (int i = 0; i < n; i++) {
		visited[planet] = true;
		if (!visited[i] && planet != i)
			go(idx + 1, i, sum + t[planet][i]);
		visited[planet] = false;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			cin >> t[i][j];
	}
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
				t[i][j] = min(t[i][j], t[i][k] + t[k][j]);
		}
	}
	go(1, k, 0);
	cout << ans;
}