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

문제 링크: https://www.acmicpc.net/problem/17182

17182번: 우주 탐사선

1. 주의할 점

- 플로이드와샬 알고리즘을 통해 미리 각 Node간 최단거리를 구해놓는다

 

2. 구현

- 각 Node간의 거리를 입력 받은 후, 플로이드 와샬 알고리즘을 사용하여 각 Node간 최단거리를 구한다

- 시작하는 행성의 Visit[]값을 True로 바꾼후, DFS()를 수행한다

- DFS(int idx, int dist, int planet) 함수는 각각 현재 행성, 현재 행성까지의 거리, 방문한 행성의 수를 매개변수로 받는다

- 현재까지 이동한 거리가 이미 구한 최단거리인 Ans보다 크다면 Return

- 모든 행성을 방문했다면, 현재까지 이동한 거리와 Ans를 비교하여 작은 값을 Ans에 저장

- 아직 방문하지 않은 행성이라면 방문처리후, DFS()를 수행한다. 간선의 값에는 음수가 없으므로 방문한 행성을 또 할 수 있지만, 방문하지 않아도 정답이 도출된다(잘 생각해보면, 순서를 바꿔서 방문하면 되기때문)

 

#define MAX 9876543210
#include <iostream>
#include <algorithm>
using namespace std;
int node, start, arr[10][10], ans = MAX;
bool visit[10] = { false, };

void dfs(int idx, int dist, int planet) {
	if (ans < dist) return;
	if (planet == node) {
		ans = min(ans, dist);
		return;
	}
	for (int i = 0; i < node; i++) {
		if (visit[i]) continue;
		visit[i] = true;
		dfs(i, dist + arr[idx][i], planet + 1);
		visit[i] = false;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> node >> start;
	for (int i = 0; i < node; i++)
		for (int j = 0; j < node; j++) 
			cin >> arr[i][j];		
	visit[start] = true;

	for (int k = 0; k < node; k++) 
		for (int i = 0; i < node; i++)
			for (int j = 0; j < node; j++)
				if (arr[i][j] > arr[i][k] + arr[k][j])
					arr[i][j] = arr[i][k] + arr[k][j];
	dfs(start, 0, 1);
	cout << ans;
	return 0;
}