백준 17182 c++ "우주 탐사선" -[PlusUltraCode]

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

17182번: 우주 탐사선

 

[필자 사고]

이 문제는 플로이드와샬 알고리즘을 이용해야 된다.

 

이 문제의 특이한 점은 플로이드 와샬만 이용하는게 아닌 어떤 경로로 가야지 최소 비용으로 모든 지역을 탐사할 수 있는지 배울 수 있는 문제이다.

 

필자는 DFS알고리즘을 이용하여 최소 비용으로 모든 지역을 탐사하는 방식을 택했다.

 

DFS알고리즘의 매력이라고 말할거 같으면 이미 방문한곳이 쓰잘대기 없는 곳이라면 다시 방문 안한상태로 바꿀 수 있다는 점이다. 

 

visited[i] = true;

DFS()

visited[i] =false; 

 

이런식으로 코드를 작성하면 수월하게 문제를 해결할 수 있다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<vector<int>> Arr;
int N, Start;
int Result = 9999999;
vector<bool> visited;

void Input() {
	cin >> N >> Start;
	Arr.resize(N);
	visited.resize(N, false);
	for (int i = 0; i < N; i++) {
		Arr[i].resize(N);
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cin >> Arr[i][k];
		}
	}

}

void Floyd_Warshall() {
	for (int k = 0; k < N; k++) {
		for (int s = 0; s < N; s++) {
			for (int e = 0; e < N; e++) {
				if (s == e)continue;
				if (Arr[s][e] > Arr[s][k] + Arr[k][e]) {
					Arr[s][e] = Arr[s][k] + Arr[k][e];
				}
			}
		}
	}
}
void DFS(int nowIdx, int dist, int count) {
	if (dist>Result) {
		return;
	}
	if (count == N) {
		Result = min(Result, dist);
		return;
	}
	for (int i = 0; i < N; i++) {
		if (visited[i] == true)continue;
		visited[i] = true;
		DFS(i, dist + Arr[nowIdx][i], count + 1);
		visited[i] = false;
	}
}

int main(void) {
	Input();
	Floyd_Warshall();
	visited[Start] = true;
	DFS(Start, 0, 1);
	cout << Result;
}